Handshaking Lemma

Handshaking Lemma and Degree Analysis

The Handshaking Lemma states that the sum of all vertex degrees in a graph $G$ equals twice the number of edges:

This arises because each edge contributes to the degree of two vertices. For example, a triangle graph has three edges, and each vertex has degree 2, yielding $2+2+2=6=2\cdot 3$.

$\mathbf{\text{Example}}$
For a graph with 4 vertices and 5 edges, the sum of degrees is $2\cdot 5=10$. If degrees are $3,3,2,2$, their sum is $10$.

$\mathbf{\text{Metaphor}}$
The lemma is like splitting a bill: each edge "pays" $\text{two}$ units (one to each endpoint), so the total "cost" is twice the number of edges.

Corollary 1: Even Number of Odd-Degree Vertices

A direct consequence of the $\mathbf{\text{Handshaking Lemma}}$ is that the total sum of $\text{degrees}$ is even. Since even sums arise only when an even number of odd terms are present, there must be an even number of $\text{odd}$-$\text{degree}$ vertices.

This $\text{corollary}$ implies that any $\text{graph}$ cannot have exactly one or three or any odd count of vertices with odd $\text{degree}$.

It is a cornerstone in proofs about Eulerian trails and parity-based arguments in networks.

$\mathbf{\text{Example}}$
In a path of length $3$, the end vertices have $\text{degree}$ $1$ (odd), the middle vertex has degree $2$ (even), so there are exactly two odd-degree vertices.

$\mathbf{\text{Metaphor}}$
Odd-degree vertices come in pairs like people starting and ending a handshake chain; you can’t have an unpaired end.

Corollary 2: Existence of a High-Degree Vertex

From the identity $\sum _u{d}_G(u)=2|E(G)|$, the average $\text{degree}$ in a $\text{graph}$ with $n=|V(G)|$ vertices is

By the pigeonhole principle, some vertex must have $\text{degree}\ge \frac{2|E(G)|}{n}$, and dually, some vertex has degree $\le \frac{2|E(G)|}{n}$.

This $\text{corollary}$ guarantees the presence of a well-connected hub or a sparsely connected leaf relative to the average.

$\mathbf{\text{Example}}$
If $|E(G)|=10$ and $|V(G)|=5$, the average degree is $4$, so at least one vertex has degree $\ge 4$.

$\mathbf{\text{Metaphor}}$
In any group of people, someone must have at least the average number of friends, and someone no more than the average.

Complement Graph Degree Calculation

To compute $d_{\bar{G}}(v)$ in terms of $d_G(v)$, note that the complement graph $\bar{G}$ includes all non-adjacent edges of $G$. Thus:

This formula accounts for all possible connections except those in $G$ and the vertex itself.

$\mathbf{\text{Example}}$
If $G$ has 5 vertices and $d_G(v)=2$, then $d_{\bar{G}}(v)=5-1-2=2$.

$\mathbf{\text{Metaphor}}$
The complement graph is like a photo negative: $\text{dark}$ areas (edges) in $G$ become $\text{light}$ in $\bar{G}$, and vice versa.

Tree Degree Bound by Leaves

In a tree $T$, every vertex’s degree is bounded above by the number of leaves. This holds because:

1. Leaves have degree 1.
2. Internal vertices split paths, creating new leaves.
3. The formula $L=2+\sum _{v\in T}(d(v)-2)$ ensures $L\ge max(d(v))$.

$\mathbf{\text{Example}}$
A star tree with 5 leaves has a central vertex of degree 5, matching the leaf count.

$\mathbf{\text{Metaphor}}$
A tree’s leaves are like audience members: the "popularity" (degree) of a speaker (vertex) cannot exceed the audience size.

Consider a $\text{tree}$ $T$, an acyclic connected $\text{graph}$ with $L$ leaves (vertices of $\text{degree}$ $1$). The problem asks whether every vertex’s $\text{degree}$ is at most $L$.

A classical argument removes a vertex $v$ of $\text{degree}$ $k$, splitting $T$ into $k$ components. Each component, being a smaller tree, has at least one leaf of $T$ not equal to $v$.

Thus there are at least $k$ distinct leaves in $T$, implying $k\le L$. In other words,

This inequality underscores how the number of endpoints (leaves) controls the maximum branching in a tree.

$\mathbf{\text{Example}}$
In a star tree with one center connected to $4$ leaves, $L=4$ and the center’s $\text{degree}$ is $4$, matching the bound.

$\mathbf{\text{Metaphor}}$
Think of a central hub with spokes to leaves; the number of spokes cannot exceed the number of endpoints on the wheel.

Conclusion

The Handshaking Lemma underpins degree analysis, while complement degrees invert adjacency logic. In trees, the leaf count inherently limits vertex degrees due to their acyclic structure. These principles illustrate how graph theory balances local properties (degrees) with global invariants (edges, leaves).