0

Consider a graph of $|V| = 2k+1$ vertices with $k+1$ of those vertices having exactly degree $2$ such that none of those degree $2$ vertices are adjacent to each other. I want to go about proving that there does not exist a Hamiltonian cycle within this graph.

I imagined that we could assume for the sake of contradiction that there existence a Hamiltonian cycle of length $2k$ in this graph. I would really like to prove that by pigeon-hole principle, there exists at least two vertices of degree $2$ that are adjacent to each other, but I am not sure if it is quite as simple as that. Anyone have recommendations on how to go about contradicting the existence of the Hamiltonian cycle?

Hanul Jeon
  • 27,376
William
  • 183

1 Answers1

2

For each degree two vertex, if there exist a Hamiltonian cycle, will contain the two edges adjacent to the vertex.

Since there are $k+1$ vertices of degree two of which none are adjacent, that means there will be $2k+2$ edges you must choose, but a Hamiltonian cycle in a graph of $2k+1$ vertices cannot have that many edges.

S. Pek
  • 380