Theorem 2.8 If a graph G has an Euler circuit, then all the vertices of G have even degree. Proof Let v be a vertex in G. If the degree of v is zero, there is nothing to prove. If the degree of v is...

Prove the following theorem of Euler.


If an undirected graph has more than two vertices of odd degree, it does not


have an Euler path.

Hint: Try a proof by contradiction, and model your argument on the proof of Theorem 2.8.

Extracted text: Theorem 2.8 If a graph G has an Euler circuit, then all the vertices of G have even degree. Proof Let v be a vertex in G. If the degree of v is zero, there is nothing to prove. If the degree of v is nonzero, then some edges on the Euler circuit touch it, and since the Euler circuit contains all of G's edges, the number of touches by these edges equals the degree of v. If we traverse the circuit, starting and ending at v, we must leave v the same number of times as we return to v. Therefore the number of touches by an edge in the Euler circuit is even. Euler's observations about paths have related proofs. These are left as exercises.