Prove that a game of Tic-Tac-Toe played on the torus can never end in a draw. (Graph theoretic solutions only.)
Here's a problem I assigned to my graph theory class. The only caveat is that I insisted that their solutions be entirely graph theoretic. Have fun with it.
Prove that a game of Tic-Tac-Toe played on the torus can never end in a draw.
The idea is to simulate the game (toroidal Tic-Tac-Toe) as a $2$-edge-coloring game on a certain bipartite graph. A win here would be tantamount to saturating a single (specific type of) vertex with edges all of one color.
This has nothing whatsoever to do with stategy or perfect play. The standard rules of Tic-Tac-Toe apply (horizontal, vertical, and diagonal wins), except that on the torus there are four additional diagonal wins.
As an example, if one coordiantes the squares of the Tic-Tac-Toe board as $(i,j)$ with $1\le i,j\le 3$, then the set $\{(1,2),(2,3),(3,1)\}$ constitutes a diagonal win on the torus. (Note that we are assuming that the Tic-Tac-Toe board covers the entirety of the torus.)
Remember that we're requesting that the proof be purely graph-theoretic, despite that it would be far easier to just list all possible endgames and note that there are no draws occurring. (PS: I have a solution to this problem.)
Let us re-interpret the tic-tac-toe game in terms of edge coloring for two associated graphs.
Note that there are $12$ total ways to win on the torus. There are $3$ horizontal lines and $3$ vertical lines. Analogously, there are $3$ diagonal lines and $3$ anti-diagonal lines. Each horizontal/vertical line pair uniquely determines a cell through their intersection. Conversely each cell belongs to precisely one such pair. The same holds for the diagonal/anti-diagonal pairs.
Let there be $6$ vertices on our first graph, one for each vertical/horizontal line. Join each vertical vertex to each horizontal vertex. The result is the complete bipartite graph $K_{3,3}$ where each edge corresponds to a cell on the playing grid. Construct the second graph through the same procedure for diagonal/anti-diagonal lines.
Now the game can be interpreted as $2$-coloring the edges of the graphs (where each move colors an edge on both graphs). Winning the game corresponds to saturating a vertex on one of the two graphs with edges of the same color. The key is now to note the following two facts:
If there exists a perfect matching with edges of the same color on one graph, then this necessarily implies the existence of a vertex saturated with the same color on the other graph.
If every vertex of $K_{3,3}$ is adjacent to edges of both color then there necessarily exists a perfect matching with edges of the same color.
It's not very difficult to prove the above two facts and I will not do so here (although the proof I have still requires a bit of case-checking, if anyone has an elegant proof of the two facts above, please share it with me). The overall interpretation here is that the game on the torus brings in a duality between vertical/horizontal wins and diagonal/anti-diagonal wins. Not winning one way forces a win the other way.
I'm not too certain what constitutes purely graph theoretic. Here is a proof that doesn't use cases.
We will show that given 5 points, there must be 3 that form a line.
Order the points $p_i$ (in whatever order you wish). Consider the pair wise difference of points $p_i - p_ j$ for $i> j$, Taken modulo 3. There are 5 points hence 10 pairs, but only 9 possibilities for their difference, thus 2 pairs of differences must be the same.
If the 2 pairs share a common point, it must be the middle point which is common, hence we get 3 points on a line and we are done.
If the 2 pairs do not share a common point, we have a parallelogram. By applying a change of basis and translation, we may assume WLOG that the points are the (1,1) (1,2) (2,1) (2,2). It is now clear that no matter where the fifth point is, we will always have a line. Hence done.