3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.