Combinatorics and Graph Theory (Guichard)

Combinatorics is often described briefly as being about counting, and indeed counting is a large part of combinatorics. As the name suggests, however, it is broader than this: it is about combining things. Questions that arise include counting problems: “How many ways can these elements be combined?” But there are other questions, such as whether a certain combination is possible, or what combination is the “best” in some sense. We will see all of these, though counting plays a particularly large role. Graph theory is concerned with various types of networks, or really models of networks called graphs. These are not the graphs of analytic geometry, but what are often described as “points connected by lines”.

Prelude to Fundamentals

Combinatorics is often described briefly as being about counting, and indeed counting is a large part of combinatorics. As the name suggests, however, it is broader than this: it is about combining things. Questions that arise include counting problems: “How many ways can these elements be combined?” But there are other questions, such as whether a certain combination is possible, or what combination is the “best” in some sense. We will see all of these, though counting plays a particularly large role.

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.