Graph Properties and the Handshaking Lemma

What is a Graph? Basic Terminology

At its heart, a graph is a simple concept. It's a way to represent connections between things. Formally, a graph $G$ is defined as a pair $(V,E)$, where:

• $V$ is a finite set of vertices (or nodes).
• $E$ is a set of edges (or arcs), where each edge connects a pair of vertices.

Think of a computer network: the computers and routers are the vertices, and the physical or logical connections between them are the edges.

Let's establish a clear vocabulary, which is critical for understanding problems accurately.

• Undirected vs. Directed Graphs: If the edges have no direction (e.g., a friendship on Facebook), the graph is undirected. The edge $(u,v)$ is the same as $(v,u)$. If the edges have a direction (e.g., following someone on Twitter), the graph is directed. The edge $(u,v)$ is an arrow from $u$ to $v$. Unless specified, GATE problems usually refer to undirected graphs.
• Adjacency and Incidence: If an edge exists between vertices $u$ and $v$, they are adjacent. The edge is said to be incident to both $u$ and $v$.
• Degree of a Vertex:
  • In an undirected graph, the degree of a vertex $v$, denoted $\mathrm{deg}(v)$, is the number of edges incident to it.
  • In a directed graph, we distinguish between in-degree (number of incoming edges) and out-degree (number of outgoing edges).
• Simple Graph: A graph with no self-loops (an edge from a vertex to itself) and no multiple edges between the same pair of vertices. This is the default assumption for most GATE problems.
• Complete Graph ($K_n$): A simple undirected graph with $n$ vertices where every pair of distinct vertices is adjacent. $K_n$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ edges. For example, $K_3$ is a triangle.

The Handshaking Lemma and Degree Sequences

A degree sequence of a graph is the list of its vertex degrees, typically written in non-increasing order. For example, for a square ($C_4$), the degree of every vertex is 2, so the degree sequence is (2, 2, 2, 2).

There's a fundamental relationship between the degrees of a graph and its number of edges. This is known as the Handshaking Lemma.

As the video explained, the Handshaking Lemma is formally stated as:
${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$

This simple formula has a powerful consequence that is frequently tested:

Corollary: In any undirected graph, the number of vertices with an odd degree must be even.

• Proof Sketch: The sum of all degrees, $2|E|$, is an even number. We can split this sum into two parts: the sum of degrees of vertices with even degree ($S_{even}$) and the sum of degrees of vertices with odd degree ($S_{odd}$).
  $S_{even}+S_{odd}=2|E|$
  Since $S_{even}$ is a sum of even numbers, it is even. Because the total sum is even, $S_{odd}$ must also be even. A sum of odd numbers can only be even if there is an even number of them. Therefore, there must be an even count of odd-degree vertices.

GATE-Style Check: Can a simple graph have a degree sequence of {3, 3, 3, 2, 1}?

1. Count odd-degree vertices: The degrees {3, 3, 3, 1} are odd. There are four such vertices. Since 4 is an even number, the graph passes this necessary condition.
2. Check the sum: The sum of degrees is $3+3+3+2+1=12$. By the Handshaking Lemma, $2|E|=12$, so the graph must have $|E|=6$ edges.

These checks are quick ways to eliminate invalid graph structures in multiple-choice questions.

Bipartite Graphs

Another fundamental property a graph can have is bipartiteness. This concept is crucial for matching algorithms and scheduling problems.

A graph is bipartite if its vertex set $V$ can be partitioned into two disjoint sets, say $U$ and $W$, such that every edge in the graph connects a vertex in $U$ to a vertex in $W$. There are no edges between two vertices in $U$, and no edges between two vertices in $W$.

A key theorem provides a simple test for bipartiteness:
Theorem: A graph is bipartite if and only if it has no odd-length cycles.

How can we test this efficiently? By trying to "2-color" the graph.

Let's solidify this with two classic examples:

• Cycle $C_4$ (a square):

  1. Let the vertices be $v_1,v_2,v_3,v_4$ in order.
  2. Color $v_1$ Red.
  3. Its neighbors, $v_2$ and $v_4$, must be Blue.
  4. The neighbor of $v_2$ (other than $v_1$) is $v_3$. It must be Red.
  5. Now check all edges. The edge $(v_3,v_4)$ connects a Red vertex to a Blue one. No conflicts.
  6. The partition is $U=\{v_1,v_3\}$ (Red) and $W=\{v_2,v_4\}$ (Blue). Thus, $C_4$ is bipartite.

• Cycle $C_3$ (a triangle):

  1. Let the vertices be $v_1,v_2,v_3$.
  2. Color $v_1$ Red.
  3. Its neighbors, $v_2$ and $v_3$, must be Blue.
  4. But $v_2$ and $v_3$ are adjacent! We have an edge connecting two Blue vertices. This is a conflict.
  5. Therefore, $C_3$ is not bipartite. This is because it is a cycle of odd length (3).

Any graph containing a triangle (like $K_3,K_4,K_5,\dots$) cannot be bipartite. Trees, on the other hand, have no cycles at all, so they are always bipartite.

Conclusion

In this lesson, we have laid the groundwork for our study of graph theory. We defined the basic components of graphs and established a vocabulary that will serve us throughout this module and beyond.

Key Takeaways:

• A graph is a set of vertices and edges. Key distinctions include directed vs. undirected and simple vs. multigraph.
• The Handshaking Lemma ($\sum \mathrm{deg}(v)=2|E|$) provides a fundamental constraint on the structure of any graph.
• A direct result of this lemma is that the number of odd-degree vertices is always even, a quick and useful check for GATE problems.
• A graph is bipartite if it can be 2-colored without conflict, which is equivalent to saying it has no odd-length cycles.

With these fundamental properties in hand, we are now ready to start exploring graphs algorithmically. In the next lesson, we will introduce Depth-First Search (DFS), a powerful traversal technique that allows us to discover the structure of a graph, including its connected components, cut vertices, and cut edges.