SUMMER FUN: #8

Let's convert the problem to a more workable formulation - each member is now a vertex in a graph, and any two people who don't dislike each other get connected by an edge. Note that each person is connected to at least half of the total members. We now need to prove the existence of a Hamiltonian cycle in this graph. We do so by induction on the number of members.

First consider the base case, the one with $4$ members, each connected to at least $2$ others. Let $m_1,m_2,m_3,m_4$ be the $4$ members of the council. Assume WLOG $m_1$ is connected to $m_2$ and $m_3$ . If $m_2$ is connected to $m_3$ , then since $m_4$ needs to be connected to at least two members, WLOG let them be $m_2$ and $m_3$ , we have a Hamiltonian cycle $(m_1,m_2,m_4,m_3,m_1)$ . Otherwise, $m_2$ isn't connected to $m_3$ , so they're both connected to $m_4$ , and again we have the cycle $(m_1,m_2,m_4,m_3,m_1)$ .

Now assume we've proven the existence of a Hamiltonian cycle for any "half-connected" graph of $2n$ members, namely one with each person connected to at least $n$ others. We now need to prove a Hamiltonian cycle exists in a half-connected graph of $2n+2$ members, and we'll be done.

Since a Hamiltonian cycle always exists in the case for $2n$ , we might as well assume those are all the connections made in the graph so far, and consider the different cases for the remaining edges' positions. We now add the two new points to the graph, so that the graph looks something like below, the greens being the two new members, $X$ and $Y$ . Also assume we've numbered the members of the $2n$ -long cycle so that $m_k$ is connected to $m_{k-1}$ and $m_{k+1}$ for $1<k<2n$ , and $m_1$ to $m_{2n}$ .

First assume the two new points aren't connected to each other. Since each vertex needs to be connected to at least $n+1$ others, by the pigeonhole principle $X$ must be connected to at least two consecutive members, $m_k$ and $m_{k+1}$ , of the $2n$ -long cycle, making a cycle of $2n+1$ members, namely $(m_k,m_{k-1},m_{k-2},...m_1,m_{2n},m_{2n-1},...,m_{k+1},X,m_k)$ . Using a similar argument for $Y$ , who needs to connect to at least $n+1$ members of a $2n+1$ long cycle, again by the pigeonhole principle he is connected to two consecutive members of the cycle, meaning a Hamiltonian cycle is now formed.

Therefore the two new points must be connected to each other. Again, if $X$ is connected to $m_k$ and $Y$ is connected to $m_{k+1}$ or vice versa, a Hamiltonian cycle will form, namely $(X,m_k,m_{k-1},...,m_1,m_{2n},m_{2n-1},...,m_{k+1},Y,X)$ . Therefore the only way to temporarily escape forming a Hamiltonian cycle is to connect $X$ and $Y$ both to, say, each of the blue points in the picture, since otherwise we'll be in the previous case of $X$ being connected to $m_k$ and $Y$ to $m_{k+1}$ . We now consider the connections formed by the red points, $m_1,m_3,...,m_{2n-1}$ .

If any two of these points are connected, say $m_1$ and $m_{2k+1}$ , a Hamiltonian cycle arises, namely $(m_1,m_2,...,m_{2k},X,Y,m_{2n},m_{2n-1},...,m_{2k+1},m_1)$ . Therefore no two red points can be connected, but by the pigeonhole principle that's impossible, since a red point needs to make at least $n+1$ connections with $n$ blue points. Therefore a Hamiltonian cycle must exist for any "half-connected" graph of $2n>2$ points, and $12$ is no exception.