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

2

For part (2), consider the situation where the guests are partitioned into two groups of five where each person in a group is friends with all the others in their group (so the friendship graph would consist of two disjoint copies of $K_5$). What would happen?

2

For part (1). Prove that the graph is hamiltonian (as Chris Eagle mentions in his comment), and then look at perfect matchings.

2

For (4), start with disjoint copies of $K_5$ and $K_6$, and identify one vertex of $K_5$ with one vertex of $K_6$. The resulting graph will have ten vertices: four of degree $4$, five of degree $5$, and one of degree $9$. Show that the vertex of degree $9$ is an obstacle to finding a Hamilton circuit.