Meeting People at a Party Hamiltonian Graph

Question

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

Answer 1

You are trying to use the Dirac Theorem . You can use instead the stronger Ore Theorem:

If $G$ is a simple graph with $n \geq 3$ vertices such that for all $u,v$ non-adjacent vertices we have $$\deg(u)+\deg(v) \geq n$$ then $G$ is Hamiltonian.

In your case you need to make sure that $6+6 \geq 10$ and $4+6 \geq 10$.

Answer 2

Temporarily ignore Ben. Then you have a graph on 9 vertices, each of degree at least 5, so the theorem you mention applies, and there's a Hamiltonian cycle.

Now bring Ben back in. He met 4 people. If two of these four are adjacent in your cycle, you can just insert Ben, and you win. If no two of the four are adjacent, then there must be two of the four that are separated by just one other guest in the cycle. Connect those two to Ben, instead, and you get a cycle of length 9, this time including Ben, but leaving out that other guest.

But that other guest met 5 of the nine in the cycle, two of whom must be adjacent in the cycle, so you can reintroduce him, getting your cycle of 10.