At a dinner party, there are $2n$ guests to be seated at a round table. Each guest knows $n$ of the other guests. Show that it is possible to seat the guests so that each is between two acquaintances.
I have done some trial and error just by brute force, and so I know that it is true. However, since it is not specified which $n$ guests are known (i.e. all odds and all evens), I am struggling with coming up with an algorithm.
This leads me to think that it might be able to be shown using induction where the inductive hypothesis is that $2n$ guests can be seated so that each is between two acquaintances. I would then need to show that it is also possible for $2n+2$ guests where each knows $n+1$ other guests. However, I do now know where to go from there, or if induction would even really work.
Hint: Let $G$ be the graph whose $2n$ vertices are the guests, and two vertices are connected by an edge if the two guests are acquainted. What would a correct seating arrangement look like, translated to this graph?