Graph Theory Basics - Key Proof

The Handshaking Lemma is one of the most fundamental results in graph theory, relating vertex degrees to edge count.

DefinitionHandshaking Lemma

In any graph $G = (V, E)$ , the sum of all vertex degrees equals twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|$

Corollary: Every graph has an even number of vertices with odd degree.

Proof of Handshaking Lemma:

We count the total number of edge-endpoint incidences in two ways.

Method 1 (counting by vertices): For each vertex $v$ , the degree $\deg(v)$ counts how many edges are incident to $v$ . Summing over all vertices counts each edge-endpoint pair once: $\sum_{v \in V} \deg(v)$

Method 2 (counting by edges): Each edge has exactly two endpoints. Therefore, each edge contributes 2 to the total count of edge-endpoint incidences: $2|E|$

Since both methods count the same thing, we have: $\sum_{v \in V} \deg(v) = 2|E|$

This completes the proof. $\square$

Proof of Corollary:

Let $V_{\text{odd}}$ be the set of vertices with odd degree and $V_{\text{even}}$ be the set of vertices with even degree. Then: $\sum_{v \in V} \deg(v) = \sum_{v \in V_{\text{odd}}} \deg(v) + \sum_{v \in V_{\text{even}}} \deg(v)$

The left side equals $2|E|$ , which is even. The second term on the right (sum of even numbers) is even. Therefore, the first term must also be even.

But this term is a sum of odd numbers (one for each vertex in $V_{\text{odd}}$ ). A sum of odd numbers is even if and only if there are an even number of terms. Therefore, $|V_{\text{odd}}|$ must be even. $\square$

ExampleApplication: Graph Non-existence

Can there exist a graph with 7 vertices having degrees 6, 5, 5, 4, 3, 2, 1?

Check the sum: $6 + 5 + 5 + 4 + 3 + 2 + 1 = 26$ .

Since 26 is even, the handshaking lemma is satisfied. However, we need to check realizability.

The vertex of degree 6 must be connected to all other 6 vertices (since there are only 7 vertices total, this vertex connects to everyone else). But then all other vertices must have degree at least 1 (connected to this vertex). The vertex with claimed degree 0... wait, our sequence has minimum degree 1, so this is possible so far.

Actually, the Erdős-Gallai theorem provides necessary and sufficient conditions for a sequence to be a valid degree sequence, which is more subtle than just checking even sum and odd-vertex count.

ExampleTournament Application

In a tournament (complete directed graph), the sum of all out-degrees equals the number of edges. If there are $n$ vertices, there are $\binom{n}{2}$ edges, so: $\sum_{v \in V} \deg^+(v) = \binom{n}{2} = \frac{n(n-1)}{2}$

The average out-degree is $\frac{n-1}{2}$ , so at least one vertex must have out-degree at least $\frac{n-1}{2}$ (i.e., wins at least half its games).

Remark

The handshaking lemma, despite its simplicity, has numerous applications. In chemistry, it constrains molecular structures (valence bonds). In computer science, it bounds the number of operations in network protocols. The name comes from a social analogy: if we count handshakes at a party by asking each person how many hands they shook, we count each handshake twice (once from each participant's perspective). This double-counting principle appears throughout combinatorics and graph theory, often providing elegant proofs by considering the same objects from two different viewpoints.