Consider vertex $v$ in graph $G$. Let $v$ have at least three adjacent vertices with degrees of two. Prove that $G$ is not a Hamiltonian graph.
Proof
Suppose $G$ is Hamiltonian.
Let $x$, $y$ and $z$ be the vertex adjacent to $v$.
We know that $G$ contains at least 4 vertices: $v$, $x$, $y$ and $z$.
$G$ must contain at least one more vertex $w$ because otherwise the sum of all degrees ($2+2+2+3=9$) would not equal twice the number of edges ($2\cdot 4=8$).
Now, there cannot be an edge between any of the edges $x$, $y$ and $z$, because that would create a cycle, e.g. $vxyv$. If we tried to construct a Hamiltonian cycle, there would be no way to "exit" without passing through the same vertex twice and whatever we try to do (i.e add more vertices), this problem still occurs.
Thus $G$ cannot be Hamiltonian.
Another approach I tried
Suppose $G$ is Hamiltonian with $n$ vertices.
Let $x$, $y$ and $z$ be the vertex adjacent to $v$.
From Dirac's theorem it follows that each vertex must have a degree of $\frac{n}{2}$ and therefore for all pairs of adjacent vertices the sum of their degrees must equal at least $n$.
$G$ must contain at least one more vertex $w$ because otherwise the sum of all degrees ($2+2+2+3=9$) would not equal twice the number of edges ($2\cdot 4=8$).
So $n\geq5$ and therefore there can be no edges between any of the pairs $x$, $y$ and $z$, because $2+2<5$.
…
Now there should be a way to reach a contradiction here but I don't really know how.
Any help or tips are much appreciated!
Best Answer
If $\ x,y,z\ $ are adjacent to $\ v\ $ and have degree two, then each of them is adjacent to exactly one other vertex, $\ x\ $ to $\ x'\ne v\ $, $\ y\ $ to $\ y'\ne v\ $ and $\ z\ $ to $\ z'\ne v\ $, say. Now each vertex of a Hamiltonian cycle must be incident on exactly two of its edges, and since any Hamiltonian cycle of $\ G\ $ must pass through $\ x\ $, $\ y\ $ and $\ z\ $, it must therefore include both of the edges incident on each of them. In particular, it must include all three of the edges $\ \{x,v\}\ $, $\ \{y,v\}\ $ and $\ \{z,v\}\ $. But this would require $\ v\ $ to be incident on at least three edges of the cycle, which is impossible.