In the previous post Fun with Hex, I asserted without proof that the Hex Game will never result a draw. In Jiri Matousek’s An Invitation to Discrete Mathematics, I found an elegant proof for the assertion, which requires only a little bit of elementary graph theory. The idea of the proof can also prove Sperner’s Lemma. Moreover, I will present later how to extrapolate this idea to discover something new. The only bit of elementary graph theory we are going to use is the Handshaking lemma.
Lemma (handshaking). Every finite undirected graph has an even number of vertices with odd degree.
To prove the lemma, simply observe that the sum of the degrees of all vertices is equal to twice the number of the edges, which should be even.
Now let us review the Hex Game. Recall two versions of the Hex Game.
The original version of the game is to color the hexagons of the game board (illustrated in black) and each player tries to link the opposite sides of the board with a connected series of hexagons with the same color.
Alternatively, one can play with the Voronoi dual of the hexagon game board (illustrated in red). This time, two players color the vertices and compete to link the opposite sides with a path of vertices of their own color. For instance, player one would try to form a red path from the northwest side to the southeast side, while player two would strive to build a blue one from the northeast side to the southwest side.
We can tilt and rescale the dual graph without changing the game as follows.
In this new graph, the first player wants to build a red path from the west to the east and the second player wants to build a blue path from the north to the south. Furthermore, for purpose of the proof, we add four auxiliary vertices on each side and color them according to which player it belongs to.
As are shown in the above graph, the vertices on the west and the east are red and the ones on the north and the south are blue. Our goal is to prove that no matter how you color the remaining vertices with red and blue, there is always a monochromatic path connecting two of the four auxiliary points. For the coloring below, there is a red path from W to E.
Proof.Assume, for the sake of contradiction, that some coloring does not form any red path from W to E or blue path from N to S. First, for every red vertex unreachable by any red path starting from W, we change it to green. Similarly, for every blue vertex unreachable by any blue path starting from N, we change it to green, too.
Under the assumption that there is no red path from W to E and no blue path from N to S, the vertices E and S are both changed to green. Now we have a triangulated planar graph whose four vertices on the external face, W, N, E, S are colored by red, blue, green, green respectively.
Lemma. Given a 3-coloring on a triangulated planar graph whose four vertices on the external face, say W, N, E, S, are colored by red, blue, green, green respectively. There is an internal triangular face whose vertices are of different color.
By this lemma, we can conclude that there exists an internal triangular face, say ABC, such that A is red, B blue and C green. This implies that there are a red path from W to A and a blue path from N to B. If the vertex C is originally red, then it should still be red because there is an edge between A and C. By the same reason, if it is originally blue, then it should still be blue. This gives a contradiction! To finish the proof for the Hex Game, we only need to prove the lemma.
Proof of Lemma. For each face of the triangulated planar graph, we put a vertex in it. Two vertices are adjacent if and only if their corresponding faces share a common edge whose endpoints are colored red and blue.
Note that the degree of the vertex in the external face is 1. By the handshaking lemma, there is a vertex, say v in the internal face, say F, whose degree is odd. It is easy to see the only possible coloring of the vertices of F to get an odd degree of v is to color them by 3 different colors. [qed]
Now I am going to show something new. The idea to consider another game board which looks like:
The idea is to get a symmetric board. To build such a game board, one can start with a hexagon in the center and then add several layers of hexagons around it. In the picture above, the hexagon labeled by 1 is the one we start with. We call it the 1st layer. Then we can add 6 hexagons labeled by 2 around it to form the 2nd layer and another 12 hexagons labeled by 3 around the 2nd layer. In general, to build a symmetric Hex of size n, one only needs to repeat the process n times.
For this symmetric Hex game board, we have three pairs of opposite sides. One reasonable goal, which is analogous to the goal of the Hex Game, is to build a monochromatic path that links two opposite sides. However two players can cooperate to tie the game in this case.
Therefore, for the symmetric Hex, the goal is to build a monochromatic connected component that touches two opposite sides or three nonadjacent sides. For simplicity, we can such a monochromatic connected component a winning component. In other words, if we label six sides by 1 through 6, both players want to use their own colors to connect side 1 and 4, or side 2 and 5, or side 3 and 6, or side 1, 3 and 5, or side 2, 4 and 6. Again, we will only consider its dual variant in the sense that each player colors the vertex of the following graph.
Proposition. The Symmetric Hex Game can never end in a tie.
Proof. Assume, for the sake of contradiction, that there is a 2-coloring of the symmetric Hex that contains no winning component. Consider the graph with 4 extra vertices W, E, N, S which connect to the vertices of the original graph as follows.
To be specific, W connects to all the vertices on side 5, E the vertices on side 2, N the vertices on side 1 and 6, S the vertices on side 3 and 4.
By the same argument we used in the proof of the Hex Game, there is either a red path from W to E or a blue path from N to S. In other words, we should have one of the following schematic pictures.
By our assumption, it must look like the pictures on the second row. Without loss of generality, assume that we have the first picture on the second row and the blue path connects vertices a and b.
Now we change the way the extra 4 vertices connect to the vertices on the boundary as follows.
Again, there is either a blue path from W to E or a red path from N to S. If there is a blue path from W to E, then this path combined with the blue path from a to b gives us a connected component that touches two opposite sides or 3 nonadjacent sides. Therefore it has to be the case that a red path connects N to S.
To summarize, whenever we have a blue path P_1 that connects side 4 and 6, there is be a red path P_2 connecting the same sides on its right side. By symmetry, there is a blue path P_3 connecting side 4 and 6 on P_2‘s right side. We can keep going and get an infinite sequence of paths connecting side 4 and 6 with alternating colors, which is impossible! [qed]
Corollary. For any 2-coloring of the symmetric Hex board of size n, there is a monochromatic connected component of size at least 2n+1.
Proof. By the symmetric Hex theorem, there is a monochromatic connected component that touches 2 opposite sides or 3 nonadjacent sides. In either case, the size of the component is at least 2n+1. [qed]