390
CHAPTER 6 Graph Theory
9. Prove that a cycle and the complement of any spanning tree must have at least one
edge in common.
10. Let Ti and T2 be two spanning trees of a graph G. Prove that if a is any edge in T1,
then there exists an edge b in T2 such that the graph obtained from T 1 by replacing a
with b is a spanning tree of G.
11. Prove that a graph G is connected if and only if G contains a spanning tree.
12. Find a MCST in the graph shown:
a
12
2
4
1
9 1e)3
d
h
f
b
8
5
10
7
/6
C
13. For the following graphs:
(a) Find a MCST in each of the graphs G 1 , G 2 , and G 3 .
(b) Repeat part (a) for graph G 1 if it must include (3, 5) and (1, 7) in the MCST.
(c) Repeat part (a) for graph G 2 if it must include (3, 10), (6, 11), and (8, 9) in the
MCST.
(d) Repeat part (a) for graph G 3 if it must include (2, 9), (6, 8), and (4, 5) in the MCST.
2 7
3
23344
2
2
5
2
2 2
2~2
3
4
6
4
6 9
310,
11
8
5 1 5 4
8
3
N31 ,
6
34
10 4
6~ 2
7
2
3V
3
2
5
6
2
3
S
7 4
7 58
67
56
6-3 -
G,
G2
G3
14. Find a MCST in each of the graphs G and H:
1
1
3
2
2
2
35
2
5
7
Z
2
33
3
4 7
5
4
3
3
G
H
(a) Is the MCST for graph G unique? If not, find all examples. Find an MCST in
the graph if (6, 3) may not be included. Is such an MCST unique? If not, find all
examples.