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

CHAP. 8] GRAPH THEORY 179

8.3. Consider the multigraphs in Fig. 8-37.

(a) Which of them are connected? If a graph is not connected, find its connected components.

(b) Which are cycle-free (without cycles)?

(c) Which are loop-free (without loops)?

(d) Which are (simple) graphs?

(a) Only (1) and (3) are connected, (2) is disconnected; its connected components are{A, D, E}and{B, C}. (4) is

disconnected; its connected components are{A, B, E}and{C, D}.

(b) Only (1) and (4) are cycle-free. (2) has the cycle(A,D,E,A), and (3) has the cycle(A,B,E,A).

(c) Only (4) has a loop which is{B, B}.

(d) Only (1) and (2) are graphs. Multigraph (3) has multiple edges{A, E}and{A, E}; and (4) has both multiple edges

{C, D}and{C, D}and a loop{B, B}.

Fig. 8-37

8.4. LetGbe the graph in Fig. 8-38(a). Find:

(a) all simple paths fromAtoC;(d) G−Y;

(b) all cycles; (e) all cut points;

(c) subgraphHgenerated byV′={B, C, X, Y};(f) all bridges.

(a) There are two simple paths fromAtoC:(A,X,Y,C)and(A,X,B,Y,C).

(b) There is only one cycle:(B,X,Y,B).

(c) As pictured in Fig. 8-38(b),Hconsists of the verticesV′and the setE′of all edges whose endpoints belong toV′,

that is,E′=[{B, X},{X, Y},{B, Y},{C, Y}].

(d) Delete vertexYfromGand all edges which containYto obtain the graphG−Yin Fig. 8-38(c). (NoteYis a

cutpoint sinceG−Yis disconnected.)

(e) VerticesA,X, andYare cut points.

(f) An edgeeis a bridge ifG−eis disconnected. Thus there are three bridges:{A, Z},{A, X}, and{C, Y}.

Fig. 8-38