
# 1.2: Examples


Suppose we have a chess board, and a collection of tiles, like dominoes, each of which is the size of two squares on the chess board. Can the chess board be covered by the dominoes? First we need to be clear on the rules: the board is covered if the dominoes are laid down so that each covers exactly two squares of the board; no dominoes overlap; and every square is covered. The answer is easy: simply by laying out 32 dominoes in rows, the board can be covered. To make the problem more interesting, we allow the board to be rectangular of any size, and we allow some squares to be removed from the board. What can be say about whether the remaining board can be covered? This is such a board, for example:

What can we say? Here is an easy observation: each domino must cover two squares, so the total number of squares must be even; the board above has an even number of squares. Is that enough? It is not too hard to convince yourself that this board cannot be covered; is there some general principle at work? Suppose we redraw the board to emphasize that it really is part of a chess board:

Aha! Every tile must cover one white and one gray square, but there are four of the former and six of the latter, so it is impossible. Now do we have the whole picture? No; for example:

The gray square at the upper right clearly cannot be covered. Unfortunately it is not easy to state a condition that fully characterizes the boards that can be covered; we will see this problem again. Let us note, however, that this problem can also be represented as a graph problem. We introduce a vertex corresponding to each square, and connect two vertices by an edge if their associated squares can be covered by a single domino; here is the previous board:

Here the top row of vertices represents the gray squares, the bottom row the white squares. A domino now corresponds to an edge; a covering by dominoes corresponds to a collection of edges that share no endpoints and that are incident with (that is, touch) all six vertices. Since no edge is incident with the top left vertex, there is no cover.

Perhaps the most famous problem in graph theory concerns map coloring: Given a map of some countries, how many colors are required to color the map so that countries sharing a border get different colors? It was long conjectured that any map could be colored with four colors, and this was finally proved in 1976. Here is an example of a small map, colored with four colors:

1.2: Examples is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard.