Chapter 4
Three Important Crossover Tactics
A crossover (first mentioned on page 54) is an idea that connects two or more differ
ent branches of math, usually in a surprising way. In this chapter, we will introduce
perhaps the three most productive crossover topics: graph theory, complex numbers,
and generating functions.
We will just scratch the surface of these three very rich topics. Our presentation
will be a mix of exposition and problems for you to ponder on the spot. You may find it
worthwhile to read Chapters 5-7 first or at least concurrently, as some of the examples
below involve relatively sophisticated mathematics.4.1 Graph Theory
The concept of a graph is very simple: merely a finite collection of vertices and edges.
The vertices are usually visualized as dots, and the edges as lines that connect some
or all of the pairs of vertices. If two vertices are connected by an edge, they are called
neighbors. By convention, graphs do not contain multiple edges (two or more edges
connecting the same pair of vertices) or loops (an edge connecting a vertex to itself).
If there are multiple edges or loops, we use the term multigraph. In the figure below,
the object on the left is a graph, while its neighbor to the right is a multigraph.You have already seen many examples of graphs. The Affirmative Action problem
(Example 2. 1.9 on page 21) can be restated as a problem about graphs as follows.
Given an arbitrary graph, show that it is possible to color the vertices
black and white in such a way that each white vertex has at least as
many black neighbors as white neighbors, and vice versa.
Likewise, the Handshake problem (1.1.4) and the solution to the Gallery problem
(2.4.3) both can be reformulated as questions about graphs, rather than people and
handshakes or networks of pipes.
This is what makes graph theory surprisingly useful. Just about any situation in
volving "relationships" between "objects" can be recast as a graph, where the vertices109