Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 185

Fig. 8-49

8.19. Prove Theorem 8.11: The following are equivalent for a graphG: (i)Gis 2-colorable. (ii)Gis bipartite.

(iii) Every cycle ofGhas even length.

(i) implies(ii). SupposeGis 2-colorable. LetMbe the set of vertices painted the first color, and letNbe the set of

vertices painted the second color. ThenMandNform a bipartite partition of the vertices ofGsince neither the

vertices ofMnor the vertices ofNcan be adjacent to each other since they are of the same color.

(ii) implies(iii). SupposeGis bipartite andMandNform a bipartite partition of the vertices ofG. If a cycle begins

at a vertexuof, say,M, then it will go to a vertex ofN, and then to a vertex ofM, and then toNand so on. Hence

when the cycle returns touit must be of even length. That is, every cycle ofGwill have even length.

(iii) implies(i). Lastly, suppose every cycle ofGhas even length. We pick a vertex in each connected component and

paint it the first color, say red. We then successively paint all the vertices as follows: If a vertex is painted red,

then any vertex adjacent to it will be painted the second color, say blue. If a vertex is painted blue, then any vertex

adjacent to it will be painted red. Since every cycle has even length, no adjacent vertices will be painted the same

color. HenceGis 2-colorable, and the theorem is proved.

8.20. Prove Theorem 8.12: A planar graphGis 5-colorable.

The proof is by induction on the numberpof vertices ofG.Ifp≤5, then the theorem obviously holds. Suppose

p>5, and the theorem holds for graphs with less thanpvertices. By the preceding problem,Ghas a vertexvsuch that

deg(v)≤5. By induction, the subgraphG−vis 5-colorable. Assume one such coloring. If the vertices adjacent tov

use less than the five colors, than we simply paintvwith one of the remaining colors and obtain a 5-coloring ofG.We

are still left with the case thatvis adjacent to five vertices which are painted different colors. Say the vertices, moving

counterclockwise aboutv, arev 1 ,...,v 5 and are painted respectively by the colorsc 1 ,...,c 5. (See Fig. 8-50(a).)

Fig. 8-50

Consider now the subgraphHofGgenerated by the vertices paintedc 1 andc 3. NoteHincludesv 1 andv 3 .Ifv 1

andv 3 belong to different components ofH, then we can interchange the colorsc 1 andc 3 in the component containing

v 1 without destroying the coloring ofG−v. Thenv 1 andv 3 are painted byc 3 ,c 1 can be chosen to paintv, and we

have a 5-coloring ofG. On the other hand, supposev 1 andv 3 are in the same component ofH. Then there is a path

Pfromv 1 tov 3 whose vertices are painted eitherc 1 orc 3. The pathPtogether with the edges{v, v 1 }and{v, v 3 }form