AGT Tut 1.1 solution

Handshaking Lemma: Proof by Induction

Theorem

For any finite graph $G=(V,E)$, the sum of the degrees of all vertices is equal to twice the number of edges:

${\sum }_{v\in V}deg(v)=2|E|$

Proof by Induction

We will use induction on the number of edges, $m=|E|$.

Base Case: ($m=0$)

If $|E|=0$, then the graph has no edges. Therefore, all vertices have a degree of $0$. Thus:

${\sum }_{v\in V}deg(v)=0=2\cdot 0=2|E|$

The base case holds.

Inductive Hypothesis:

Assume the theorem holds for any graph with $k$ edges, where $k\ge 0$. That is, for a graph $G=(V,E)$ with $|E|=k$:

${\sum }_{v\in V}deg(v)=2k$

Inductive Step:

We need to show that the theorem holds for a graph with $k+1$ edges.

Consider a graph $G^{\prime }=(V^{\prime },E^{\prime })$ with $|E^{\prime }|=k+1$.

Remove an arbitrary edge $e=\{u,v\}$ from $G^{\prime }$. This results in a new graph $G=(V,E)$ where $V=V^{\prime }$ and $E=E^{\prime }\setminus \{e\}$, with $|E|=k$.

By the inductive hypothesis, for graph $G$:

${\sum }_{v\in V}de{g}_G(v)=2k$

Now, add the edge $e=\{u,v\}$ back to $G$ to obtain the original graph $G^{\prime }$.

• If $u\ne v$, then $de{g}_{G^{\prime }}(u)=de{g}_G(u)+1$ and $de{g}_{G^{\prime }}(v)=de{g}_G(v)+1$. For all other vertices $x$, $de{g}_{G^{\prime }}(x)=de{g}_G(x)$.
• If $u=v$ (loop), then $de{g}_{G^{\prime }}(u)=de{g}_G(u)+2$.

In either case, the sum of degrees in $G^{\prime }$ increases by $2$ compared to $G$.

Therefore:

${\sum }_{v\in V^{\prime }}de{g}_{G^{\prime }}(v)={\sum }_{v\in V}de{g}_G(v)+2=2k+2=2(k+1)=2|E^{\prime }|$

Thus, the theorem holds for a graph with $k+1$ edges.

Conclusion:

By the principle of mathematical induction, the Handshaking Lemma holds for all finite graphs:

${\sum }_{v\in V}deg(v)=2|E|$