Question: Graph Theory and Trees

Question

In a group of 2n schoolchildren each one has at least n friends. On an outing, the teacher tells them to hold hands in pairs. Show that this can be done with each child holding a friend’s hand, and that if n > 1, the choice of friends can be made in at least two different ways.

This was on a previous exam, and I have yet to receive the solutions for it. Can anyone help?

Answer 1

Name these kids by $k_1,\dots,k_{2n}$. Let us start pretty randomly, $k_1$ has a friend, say $k_2$, then let $k_1$ hold hands of $k_2$. Now consider the remaining kids. If there is friends pair, just pick them up...We just proceed until we stop. If we are lucky, every kid holds a friend. What is the situation if we are not lucky?

Suppose $(k_1,k_2),\dots, (k_{2m-1},k_{2m})$ are fine, $m<n$ , but $k_{2m+1},\dots,k_{2n}$ can not proceed. Then consider $k_{2m+1}, k_{2m+2}$, their friend must be $k_j, j\le 2m$. The situation $k_{2m+1}$ friend with $k_1$ and at the same time $k_{2m+2}$ friend with $k_2$ cannot happen, otherwise let $(k_1, k_{2m+1}), (k_2, k_{2m+2})$ we can proceed further. Therefore the number of $k_{2m+1}$'s friends plus the number of $k_{2m+2}$'s friends is no more than $2 m$, contradiction.

If $n>1$, suppose there is only one way, say $(k_{2i-1}, k_{2i})$ hold. By the same argument $k_1$'s friends plus $k_2$'s friends is not more than $2(n-1)+1+1$, by assumption, it is not less than $2n$, so equal. It follows that either $k_1$ friend with $k_{2i-1}, k_{2i}$ and $k_2$ not friend with $k_{2i-1}, k_{2i}$, or $k_2$ friend with $k_{2i-1}, k_{2i}$ and $k_1$ not friend with $k_{2i-1}$. Suppose $k_1$ friend with $k_3, k_4$ then $k_2$ not friend with $k_3, k_3$. Swapping the role of $k_3,k_4$ and $k_1, k_2$, we find a contradiction.

Answer 2

By a theorem of Ore (proof here), if every pair of non-adjacent vertices of a graph on $m$ vertices has degrees adding up to at least $m$, then the graph is Hamiltonian. This applies to the schoolchildren, with $m=2n$. So they can be ordered into a Hamiltonian cycle (a path will do), $c_1,c_2,\dots,c_{2n}$, where each $c_i$ is friends with $c_{i-1}$ and $c_{i+1}$. Now pair $c_1$ with $c_2$, $c_3$ with $c_4$, and so on.

Dirac's Theorem, a special case of Ore's Theorem, is strong enough to solve this problem. A proof is here.

EDIT: Dirac's Theorem states that if each of the $m$ vertices of a graph has degree at least $m/2$, then the graph is Hamiltonian. This is exactly the hypothesis satisfied by the schoolchild graph.