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?
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.