184 GRAPH THEORY [CHAP. 8
(a) Redrawing the positions ofBandE, we get a planar representation of the graph as in Fig. 8-47(a).
(b) This is not the star graphK 5. This has a planar representation as in Fig. 8-47(b).
(c) This graph is non-planar. The utility graphK 3 , 3 is a subgraph as shown in Fig. 8-47(c)where we have redrawn
the positions ofCandF.Fig. 8-478.16. Count the numberV of vertices, the numberEof edges, and the numberRof regions of each map in
Fig. 8-48; and verify Euler’s formula. Also find the degreedof the outside region.Fig. 8-48(a) V= 4 ,E= 6 ,R=4. HenceV−E+R= 4 − 6 + 4 = 2 .Alsod=3.
(b) V= 6 ,E= 9 ,R=5; soV−E+R= 6 − 9 + 5 =2. Hered=6 since two edges are counted twice.
(c) V= 5 ,E= 10 ,R=7. HenceV−E+R= 5 − 10 + 7 =2. Hered=5.8.17. Find the minimum numbernof colors required to paint each map in Fig. 8-48.
(a)n=4; (b)n=3; (c)n=2.8.18. Prove Theorem 8.8 (Euler):V−E+R=2.
Suppose the connected mapMconsists of a single vertexPas in Fig. 8-49(a). ThenV=1,E=0, andR=1.
HenceV−E+R=2. OtherwiseMcan be built up from a single vertex by the following two constructions:(1) Add a new vertexQ 2 and connect it to an existing vertexQ 1 by an edge which does not cross any existing
edge as in Fig. 8-49(b).
(2) Connect two existing verticesQ 1 andQ 2 by an edgeewhich does not cross any existing edge as in
Fig. 8-49(c).Neither operation changes the value ofV−E+R. HenceMhas the same value ofV−E+Ras the map consisting
of a single vertex, that is,V−E+R=2. Thus the theorem is proved.