discrete mathematicseulerian-pathgraph theory
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.
The complete bipartite graph $K_{2,4}$ has an Eulerian circuit, but is non-Hamiltonian (in fact, it doesn't even contain a Hamiltonian path).
Any Hamiltonian path would alternate colors (and there's not enough blue vertices). Since every vertex has even degree, the graph has an Eulerian circuit.
Consider the complete graph $K_5$: it has $5$ vertices, each of degree $4$, and how many edges?
Best Answer
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.$