390 CHAPTER 6 Graph Theory
- Prove that a cycle and the complement of any spanning tree must have at least one
edge in common. - 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. - Prove that a graph G is connected if and only if G contains a spanning tree.
- Find a MCST in the graph shown:
a
12 2 4
1
d^9 1e)3h f b(^8 5)
10 7 /6
C
- 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 2 3V^5 3(^2 36)
7 58 67 56 S^7 6-3 -^4
G, G2 G3
- Find a MCST in each of the graphs G and H:
1 1
3 2
2 2 35
2 5 7 Z 233
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.