Mathematics for Computer Science

11.11. References 465

c

b

a

d

f

e

h

g

Figure 11.33 The graphG.

(c)ForGewith edgeha—dideleted, explain why there cannot be two edge-
disjoint spanning trees.

Hint:: Count vertices and edges.

Problem 11.55.
Prove that ifGis a forest and

jV.G/jDjE.G/jC1; (11.8)

thenGis a tree.

Problem 11.56.
LetH 3 be the graph shown in Figure 11.34. Explain why it is impossible to find
two spanning trees ofH 3 that have no edges in common.

Exam Problems

Problem 11.57. (a)LetTbe a tree andea new edge between two vertices ofT.
Explain whyTCemust contain a cycle.

(b)Conclude thatTCemust have another spanning tree besidesT.