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

182 GRAPH THEORY [CHAP. 8

Fig. 8-43

except that two of the ways lead to disconnected graphs. Hence the above eight spanning trees are all the spanning

trees ofG.

8.12. Find a minimal spanning treeTfor the weighted graphGin Fig. 8-44(a).

Fig. 8-44

SinceGhasn=9 vertices,Tmust haven− 1 =8 edges. Apply Algorithm 8.2, that is, keep deleting edges with

maximum length and without disconnecting the graph until onlyn− 1 =8 edges remain.Alternatively, applyAlgorithm

8.3, that is, beginning with the nine vertices, keep adding edges with minimum length and without forming any circle

untiln− 1 =8 edges are added. Both methods give a minimum spanning tree such as that shown in Fig. 8-44(b).

8.13. LetGbe a graph with more than one vertex. Prove the following are equivalent.

(i) Gis a tree.

(ii) Each pair of vertices is connected by exactly one simple path.

(iii)Gis connected; butG−eis disconnected for any edgeeofG.

(iv) Gis cycle-free, but if any edge is added toGthen the resulting graph has exactly one cycle.

(i) implies(ii) Letuandvbe two vertices inG. SinceGis a tree,Gis connected so there is at least one path between

uandv. By Problem 8.37 there can only be one simple path betweenuandv, otherwiseGwill contain a cycle.

(ii) implies(iii) Suppose we delete an edgee={u, v}fromG. Noteeis a path fromutov. Suppose the resulting

graphG−ehas a pathPfromutov. ThenPandeare two distinct paths fromutov, which contradicts the

hypothesis. Thus there is no path betweenuandvinG−e,soG−eis disconnected.

(iii) implies(iv) SupposeGcontains a cycleCwhich contains an edgee={u, v}. By hypothesis,Gis connected but

G′=G−eis disconnected, withuandvbelonging to different components ofG′(Problem 8.41) This contradicts

the fact thatuandvare connected by the pathP=C−ewhich lies inG′. HenceGis cycle-free. Now letxand

ybe vertices ofGand letHbe the graph obtained by adjoining the edgee={x, y}toG. SinceGis connected,

there is a pathPfromxtoyinG; henceC=Peforms a cycle inH. SupposeHcontains another cycleC′. Since

Gis cycle-free,C′must contain the edgee, sayC′=P′e. ThenPandP′are two simple paths inGfromxtoy.

(See Fig. 8-45.) By Problem 8.37,Gcontains a cycle, which contradicts the fact thatGis cycle-free. HenceH

contains only one cycle.