Questions: Problem 4 (14pts) The Handshaking lemma states that 2e(G)=∑(v∈V(G))dG(v). Prove this using induction in two ways: (a) by induction on the number of edges e(G), and (b) by induction on the number of vertices v(G).

Solution Steps

To prove the Handshaking lemma using induction, we can approach it in two different ways:

(a) Induction on the number of edges \( e(G) \):

1. Base Case: Consider a graph with no edges. The sum of the degrees of all vertices is zero, and \( 2 \times 0 = 0 \), which satisfies the lemma.
2. Inductive Step: Assume the lemma holds for a graph with \( k \) edges. For a graph with \( k+1 \) edges, add an edge between two vertices. The degree of each of these vertices increases by 1, increasing the sum of degrees by 2, which maintains the equality.

(b) Induction on the number of vertices \( v(G) \):

1. Base Case: Consider a graph with one vertex and no edges. The sum of the degrees is zero, and \( 2 \times 0 = 0 \), which satisfies the lemma.
2. Inductive Step: Assume the lemma holds for a graph with \( n \) vertices. For a graph with \( n+1 \) vertices, consider adding a new vertex and connecting it with some existing vertices. Each connection increases the sum of degrees by 2, maintaining the equality.

To prove the Handshaking lemma \( 2e(G) = \sum_{v \in V(G)} d_G(v) \) by induction on the number of edges \( e(G) \):

• Base Case: For \( e(G) = 0 \), the graph has no edges. Thus, \( \sum_{v \in V(G)} d_G(v) = 0 \) and \( 2 \times 0 = 0 \). The base case holds.

• Inductive Step: Assume the lemma holds for a graph with \( k \) edges. For a graph with \( k+1 \) edges, we can add an edge between two vertices \( u \) and \( v \). The degrees of \( u \) and \( v \) increase by 1, so: \[ \sum_{v \in V(G)} d_G(v) + 2 = \sum_{v \in V(G)} d_G(v) + 2 \] This implies: \[ 2(k + 1) = \sum_{v \in V(G)} d_G(v) + 2 \] Therefore, the lemma holds for \( k+1 \) edges.

To prove the Handshaking lemma \( 2e(G) = \sum_{v \in V(G)} d_G(v) \) by induction on the number of vertices \( v(G) \):

• Base Case: For \( v(G) = 1 \), the graph has one vertex and no edges. Thus, \( \sum_{v \in V(G)} d_G(v) = 0 \) and \( 2 \times 0 = 0 \). The base case holds.

• Inductive Step: Assume the lemma holds for a graph with \( n \) vertices. For a graph with \( n+1 \) vertices, we can add a new vertex \( w \) and connect it to \( k \) existing vertices. The sum of the degrees becomes: \[ \sum_{v \in V(G)} d_G(v) + k \] The total number of edges is \( e(G) + k \), leading to: \[ 2(e(G) + k) = \sum_{v \in V(G)} d_G(v) + 2k \] Thus, the lemma holds for \( n+1 \) vertices.

Final Answer