CHAP. 8] GRAPH THEORY 171
Observe that any coloring of the regions of a mapMwill correspond to a coloring of the vertices of the dual
mapM∗. ThusMisn-colorable if and only if the planar graph of the dual mapM∗is vertexn-colorable. Thus
the above theorem can be restated as follows:
Four Color Theorem (Appel and Haken):If the regions of any mapMare colored so that adjacent regions
have different colors, then no more than four colors are required.
The proof of the above theorem uses computers in an essential way. Specifically,Appel and Haken first showed
that if the four color theorem was false, then there must be a counterexample among one of approximately 2000
different types of planar graphs. They then showed, using the computer, that none of these types of graphs has
such a counterexample. The examination of each different type of graph seems to be beyond the grasp of human
beings without the use of a computer. Thus the proof, unlike most proofs in mathematics, is technology dependent;
that is, it depended on the development of high-speed computers.
8.11Representing Graphs in Computer Memory
There are two standard ways of maintaining a graphGin the memory of a computer. One way, called
thesequential representationofG, is by means of its adjacency matrixA. The other way, called thelinked
representationoradjacency structureofG, uses linked lists of neighbors. Matrices are usually used when the
graphGis dense, and linked lists are usually used whenGis sparse. (A graphGwithmvertices andnedges is
said to bedensewhenm=O(n^2 )andsparsewhenm=O(n)or evenO(nlogn).)
Regardless of the way one maintains a graphGin memory, the graphGis normally input into the computer
by its formal definition, that is, as a collection of vertices and a collection of pairs of vertices (edges).
Adjacency Matrix
SupposeGis a graph withmvertices, and suppose the vertices have been ordered, say,v 1 ,v 2 ,...,vm. Then
theadjacency matrixA=[aij]of the graphGis them×mmatrix defined by
aij={
1ifviis adjacent tovj
0 otherwiseFigure 8-27(b)contains the adjacency matrix of the graphGin Fig. 8-27(a)where the vertices are orderedA,B,
C,D,E. Observe that each edge{vi,vj}ofGis represented twice, byaij=1 andaji=1. Thus, in particular,
the adjacency matrix is symmetric.
The adjacency matrixAof a graphGdoes depend on the ordering of the vertices ofG, that is, a different
ordering of the vertices yields a different adjacency matrix. However, any two such adjacency matrices are closely
related in that one can be obtained from the other by simply interchanging rows and columns. On the other hand,
the adjacency matrix does not depend on the order in which the edges (pairs of vertics) are input into the computer.
There are variations of the above representation. IfGis a multigraph, then we usually letaijdenote the
number of edges{vi,vj}. Moreover, ifGis a weighted graph, then we may letaijdenote the weight of the edge
{vi,vj}.
Fig. 8-27