Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
$1$ is a special case of Dirac's theorem – Chris Eagle May 29 '12 at 17:52

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?

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.