1. **Problem Statement:** State and prove the Handshaking Theorem and use it to show that if all vertices of an undirected graph have degree $k$, then the number of edges is a multiple of $k$. 2. **Handshaking Theorem Statement:** In any undirected graph, the sum of the degrees of all vertices equals twice the number of edges. 3. **Proof of Handshaking Theorem:** - Each edge in an undirected graph contributes exactly 2 to the total degree count because it connects two vertices. - Let the graph have $n$ vertices and $m$ edges. - Let the degree of vertex $i$ be $d_i$. - Then, the sum of degrees is $\sum_{i=1}^n d_i$. - Since each edge is counted twice (once at each endpoint), we have: $$\sum_{i=1}^n d_i = 2m$$ 4. **Using the Theorem to Show Number of Edges is Multiple of $k$:** - Given all vertices have degree $k$, so $d_i = k$ for all $i$. - Then, the sum of degrees is: $$\sum_{i=1}^n d_i = nk$$ - By the Handshaking Theorem: $$nk = 2m$$ - Rearranging for $m$: $$m = \frac{nk}{2}$$ 5. **Conclusion:** - Since $m$ is the number of edges, and $nk$ is even (because it equals $2m$), $m$ must be an integer. - Therefore, the number of edges $m$ is a multiple of $k/2$ times $n$. - Specifically, if $k$ is even, $m$ is an integer multiple of $k/2$. - In the example graph with 4 vertices each of degree 2, the number of edges is: $$m = \frac{4 \times 2}{2} = 4$$ - This matches the given graph with 4 edges. Hence, the number of edges is a multiple of $k$ when all vertices have degree $k$.