62 2. Evaluation, Division, and Expansion
Such an array of vertices and edges is called a graph. Some examples of
graphs are the following:
The graphs involved in map coloring problems can be drawn on a plane
or a sphere, but there are some graphs which cannot be drawn on a plane
surface without the edges intersecting in points other than vertices. Such
a graph is
A B c
D E F
in which each of the vertices A, B, C is connected to each of the vertices
D, E, F.
The question of coloring regions on a map can be reinterpreted as col-
oring vertices on a graph in such a way that any two vertices joined by
an edge are colored differently. Recall that a graph, in this context, is a
collection of points or vertices some pairs of which are connected by edges.
To study coloring problems in a systematic way, we define for a graph G
the chromatic function Cc(t). This is the number of ways in which the
graph G can be colored with no more than t colors so that two vertices
joined by an edge are colored differently. The Four Color Conjecture says
that, if G is a graph which can be presented on the surface of a sphere with
no crossing of edges except at vertices, then CG(~) is always at least 1.
(a) Suppose that n,. is the number of ways a graph G with a finite number
n of vertices can be colored with exactly r distinct colors. Show that
Cc(t) = 2 ( ; ) nr.
r=O
Thus the chromatic function of a graph with finitely many vertices is a
polynomial.