Discrete Math, First series, Notes, 6/22/04
REU 2004

Instructor: László Babai
Scribes: Charilaos Skiadas, Eric Patterson, and Travis Schedler

Graph of knight moves on a $4 \times 4$ chessboard.

Hint: Show that from any trail of the knight's moves, if you delete 4 cells, the trail splits into no more than 5 connected parts. (A set $S$ of cells is connected from the knight's point of view if the knight can move from any cell of $S$ to any other cell of $S$ without leaving $S$.)

$\ast\qquad\ast\qquad\ast$

Study the handout for the basic definitions involving graphs, including complete graphs, (complete) bi(multi-)partite graphs, (induced) subgraphs, the degree of a vertex, complement of a graph and Hamilton cycles. In particular, recall that an isomorphism from the graph $\mathcal{G}=(V,E)$ to the graph $\mathcal{H}=(W,F)$ is a bijection $f:V\to W$ between the vertices that preserves the adjacency relation, i.e. for any two vertices $x,y\in V$, $x,y$ are adjacent in $\mathcal{G}$ iff (if and only if) $f(x),f(y)$ are adjacent in $\mathcal{H}$. $\mathcal{G}$ is said to be isomorphic to $\mathcal{H}$ if there exists an isomorphism from $\mathcal{G}$ to $\mathcal{H}$.

$\ast\qquad\ast\qquad\ast$

We defined decision tree and the related concepts of root, node, leaves, parent, and child. For example, flipping $n$ coins can be made into a decision tree with $2^n$ leaves. Similarly, we can make a decision tree from the moves in a chess game, but the tree is more complicated. For example, the leaves will not all be at the same level since different games end after different numbers of moves. Furthermore, the possible moves at each node are dependent on the preceding moves or the history. Although the decision tree for a chess game is far too large to store in a computer (it has more configurations than the number of atoms in the earth), such trees can on principle be analyzed in a finite time for a winning strategy.

First, assign a value of B, W, or D to the leaves of the tree if the outcome is a black win, a white win, or a draw, respectively. The nodes above the leaves can be assigned a value of B, W, or D if there is an optimal strategy for black to win, white to win, or a draw. Suppose the node $x$ is a white move. Then the value of $x$ is W if $\exists$ W child of $x,$ B if all children are B, and D if there is no W child and $\exists$ D child.

Definition 2.1   A strategy function for white is a function from the set of histories preceding a white move to the set of possible next moves. A winning strategy function for white makes moves to nodes with value W.

If a winning strategy exists for white, then the root must have value W, and there is a W child all of whose children are W. Each of these children must have a W child all of whose children are W, etc.

Theorem 2.2   If a finite game only has win or lose outcomes, then one of the players has a winning strategy.

This theorem can be used to solve the Divisor Game problem. (Hint: Proof by contradiction.)

Definition 2.3   A Hamilton cycle is a subgraph that is an $n$-cycle in a graph on $n$ vertices. A graph is Hamiltonian if it has a Hamilton cycle.

Method 1. Make the vertices of the grid into the cells of a chess board. Hint: How many steps do you move to get back to your starting color? How many steps do you move to get all the cells?

Method 2. Sam's hint: Use the lemma:

Lemma 2.4   If $G$ is Hamiltonian then removing $k$ vertices splits $G$ into at most $k$ connected components.

Definition 2.5   A graph $G$ is bipartite if its vertices can be colored red and blue such that adjacent vertices have different colors.

Observe: if $G$ is bipartite and Hamiltonian, then the two parts are equal. Exercise  is a consequence of this.

Method 3. Alex's hint: What goes up, must come down. What moves left, must return to the right.

Definition 2.6   A graph $\cal G$ is bipartite if the set of vertices $V$ partitions into two disjoint subsets, $V_1$ and $V_2$ (i.e. so that $V_1 \cup V_2 = V$ and $V_1 \cap V_2 = \emptyset$) such that no vertex of $V_1$ is adjacent to any other vertex of $V_1$, and no vertex of $V_2$ is adjacent to any other vertex of $V_2$. In other words, all edges of $\cal G$ connect one vertex from $V_1$ and one vertex from $V_2$.

In other words, a graph is bipartite iff it is a subgraph of a complete bipartite graph (cf. p. 44 of the notes).