How to prove $G$ is not Hamiltonian?

482 Views Asked by At

A connected graph $G$ of order $n=2k+1$ has $k+1$ vertices of degree 2, no two of which are adjacent, while the remaining $k$ vertices have degree 3 or more. Show that $G$ is not Hamiltonian.

1

There are 1 best solutions below

0
On

If there is a Hamiltonian cycle, any edge of $G$ which is incident with a vertex of degree $2$ must be in the cycle, right? If $G$ has $2k+1$ vertices, how many edges will a Hamiltonian cycle have?