5
$\begingroup$

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

-I almost feel like you have to prove these two parts separately. I understand that to be Hamiltonian a vertex tour (a path in which all vertices are touched once) is possible on the graph, and that to be Eulerian an edge tour(a path in which all edges are touched once). Although I am not sure how to construct this in the form a proof. I also know that you can test to see if a graph is Hamiltonian if each vertex has a degree $\ge$ $\frac{1}{2}p$ where $p$ is the number of vertices in the simple graph.

$\endgroup$
4
$\begingroup$

The Hamiltonian part is immediate if you use Ore's Theorem. Let $u$ and $v$ be two distinct vertices of $G$. If $\deg(u)+\deg(v)<14$, then $G-\{u,v\}$ has at least $88-13=75$ edges, but it has $12$ vertices and $\binom{12}{2}=66<75$, contradicting the assumption that $G$ is simple. Thus, $\deg(u)+\deg(v)\geq 14$ for any pair of distinct vertices $u$ and $v$ in $G$.

Hint for the Eulerian part: Prove that $G$ has at least $8$ vertices of degree $13$.

$\endgroup$
  • 1
    $\begingroup$ Thank you, is there a specific formula that can be used for the Eularian part? $\endgroup$ – jeremysanchez50 Dec 5 '15 at 21:54

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.