SECTION 2.2 Elementary Graph Theory 143
- Prove that any cycle in a bipartite graph must have even length.
Conversely, if every cycle in a graph has even length, show that
the graph must be bipartite. - How many edges are there in the complete bipartite graphKm,n?
- LetGbe a finite simple graph (see page 109) ofnvertices in which
every vertex has degreek. Find a simple formula in terms for the
number of edges in terms ofnandk. - Let G be a planar graph. Prove that G must contain a vertex
whose degree is at most 5. - Use the result of Exercise 8 to show that any planar graph can be
6-colored. That is to say, if Gis a planar graph then using only
six colors we can color the vertices ofGin such a way that no two
adjacent vertices have the same color.^39 - Prove that none of the complete graphsKn, n≥5 is planar.
- LetGbe a planar graph and letMbe the map it determines by an
embedding in the plane. We define thedual graphG∗ (relative
to the mapM) as follows. The vertices ofG∗are the faces of M.
Next, for each edge ofGwe draw an edge between the two faces
bounded by this edge. (If this edge bounds a single face, then
a loop is created.) Show (by drawing a picture) that even when
every edge bounds two faces, then the dual graph might not be a
simple graph even whenGis a simple graph. - LetGbe a planar graph, embedded in the plane, resulting in the
mapM. Let G∗ be the dual graph relative to M. Let T be a
spanning tree inGand consider the subgraphT∗ofG∗to have all
the vertices ofG∗(i.e., all the faces ofM) and to have those edges
which corresponding to edges inGbut not in T.
(^39) Of course, the above result isn’t “best possible.” It was shown in 1976 by K. Apple and W.
Haken that any planar map can 4-colored. For a nice online account, together with a sketch
of a new proof (1997) by N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas, see
http://www.math.gatech.edu/∼thomas/FC/fourcolor.html. Both of the above-mentioned proofs are
computer aided.
It is not too difficult to prove that a planar graph can be 5-colored; see M. Aigner and G.M.
Ziegler,Proofs from the Book, Third Edition, Springer, 2004, pages 200-201.