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

Question

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

-This was a two part question, and for the first part I had to prove why the graph is Hamiltonian, but now i am struggling with proving why it is not Eularian. The hint my teacher gave me was to prove that G has at least 8 vertices of degree 13, which I unfortunately still can't solve, any help is appreciated.

Answer 1

Step 1: prove the hint. Suppose it's not true, then bound the total number of edges by bounding the edges at each vertex, and get a contradiction.

Step 2: Since $8>2$, there are more than two vertices of odd degree.

Step 3: Profit.

Answer 2

Suppose $G$ has fewer than $8$ vertices of degree $13$. Then it has at most $7$ vertices of degree $13,$ and the other $7$ vertices have degree at most $12$. Thus the sum of the degrees is at most $7\times13+7\times12=175.$ This contradicts the handshake lemma, which says that the sum of the degrees is twice the number of edges, in this case $176.$