Ten people came to my party. Each person meets at least 6 other people, except for my friend Ben who only meets four people. We make a graph H where each person is represented by a vertex, and put an edge between two people who meet. Prove that H must be Hamiltonian.
I was thinking of using the theorem that if a graph has order $n\geq 3$ and each vertex has degree at least $n/2$ then the graph is Hamiltonian. However, I can't use this because of the one vertex which only has degree four. Each vertex must have at least degree 5 for this theorem to hold.
Can I use the definition of Hamiltonian in some way? A cycle which begins and end at the same point and passes each vertex only once.
What else could I use to prove that this situation would be a Hamiltonian graph?
This is similar to the question... but the one vertex with degree 4 makes it different. Graph theory people at a round table problem