A connected simple graph G has 14 vertices and 88 edges Prov

A connected simple graph G has 14 vertices and 88 edges. Prove G is Hamiltonian, but not Eulerian.

Solution

The Hamiltonian part is immediate if you use Ore\'s Theorem. Let uu and vv be two distinct vertices of GG. If deg(u)+deg(v)<14deg(u)+deg(v)<14, then G{u,v}G{u,v} has at least 8813=758813=75 edges, but it has 1212 vertices and (122)=66<75(122)=66<75, contradicting the assumption that GG is simple. Thus, deg(u)+deg(v)14deg(u)+deg(v)14 for any pair of distinct vertices uu and vv in GG.

Hint for the Eulerian part: Prove that GG has at least 88 vertices of degree 1313.

Suppose GG has fewer than 88 vertices of degree 1313. Then it has at most 77 vertices of degree 13,13, and the other 77 vertices have degree at most 1212. Thus the sum of the degrees is at most 7×13+7×12=175.7×13+7×12=175. This contradicts the handshake lemma, which says that the sum of the degrees is twice the number of edges, in this case 176.

hence,proved.