0
$\begingroup$

It is a homework question from a introductory graph theory course.

  1. Amongst a dinner party for ten people each person has at least five friends attending. Prove that the group can be seated around a table so that everyone has a friend sitting on either side of them.
  2. This time suppose that each of the group of ten has only four friends attending. Prove that a similar seating arrangement is not always possible.
  3. What if two of the group have only four friends attending and the rest at least five each?
  4. Four with four friends , the rest at least five each.

I have no idea how to do it. Could anyone help me?

  • 0
    $1$ is a special case of [Dirac's theorem](http://en.wikipedia.org/wiki/Dirac%27s_theorem_on_Hamiltonian_cycles#Bondy.E2.80.93Chv.C3.A1tal_theorem)2012-05-29

3 Answers 3