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

186 GRAPH THEORY [CHAP. 8

a cycleCwhich encloses eitherv 2 orv 4. Consider now the subgraphKgenerated by the vertices paintedc 3 orc 4.

SinceCenclosesv 2 orv 4 , but not both, the verticesv 2 andv 4 belong to different components ofK. Thus we can

interchange the colorsc 2 andc 4 in the component containingv 2 without destroying the coloring ofG−v. Thenv 2

andv 4 are painted byc 4 , and we can choosec 2 to paintvand obtain a 5-coloring ofG. ThusGis 5-colorable and the

theorem is proved.

8.21. Use the Welch-Powell Algorithm 8.4 (Fig. 8-24) to paint the graph in Fig. 8-50(b).

First order the vertices according to decreasing degrees to obtain the sequence

H, A, D, F, B, C, E, G

Proceeding sequentially, we use the first color to paint the verticesH,B, and thenG. (We cannot paintA,D,or

Fthe first color since each is connected toH, and we cannot paintCorEthe first color since each is connected to

eitherHorB.) Proceeding sequentially with the unpainted vertices, we use the second color to paint the verticesA

andD. The remaining verticesF,C, andEcan be painted with the third color. Thus the chromatic numberncannot

be greater than 3. However, in any coloring,H,D, andEmust be painted different colors since they are connected to

each other. Hencen=3.

8.22. LetGbe a finite connected planar graph with at least three vertices. Show thatGhas at least one vertex

of degree 5 or less.

Letpbe the number of vertices andqthe number of edges ofG, and suppose deg(u)≥6 for each vertexuofG.

But 2qequals the sum of the degrees of the vertices ofG(Theorem 8.1); so 2q≥ 6 p. Therefore

q≥ 3 p> 3 p− 6

This contradicts Theorem 8.9. Thus some vertex ofGhas degree 5 or less.

SEQUENTIAL REPRESENTATION OF GRAPHS

8.23. Find the adjacency matrixA=[aij]of each graphGin Fig. 8-51.

Fig. 8-51

Setaij=nif there arenedges{vi,vj}andaij=0 otherwise. Hence:

(a) A=

⎡

⎢

⎢

⎣

0101

1011

0101

1110

⎤

⎥

⎥

⎦; (b) A=

⎡

⎢

⎢

⎣

1001

0021

0200

1101

⎤

⎥

⎥

⎦

(Since(a)has no multiple edges and no loops, the entries inAare either 0 or 1, and are 0 on the diagonal.)