- #1
TheMathNoob
- 189
- 4
Homework Statement
Let T be any spanning tree of an undirected graph G. Suppose that uv is any edge in G that is not in T. The following proofs are easy by using the definitions of undirected tree, spanning tree and cycle
a)Let G1 be the subgraph that results from adding uv to T. Show that G1 has a cycle involving uv, say (w1,w2,...wp,w1, where p>=3, u =w1 and v=wp
b) Suppose anyone edge wi,wi+1, is removed from the cycle created in part(a), creating a subgraph G2(which depends on i). Show that G2 is a spanning tree for G
Homework Equations
I think that this is relevant in this proof, any free tree with N vertices has N-1 edges. "The book did not give any hint".
The Attempt at a Solution
a)Let n be the number of vertices of an undirected graph. Therefore, its minimum spanning tree will have n-1 edges. A spanning tree in this case is also a connected acyclic graph which has the same property. If we add 1 more edge from G that is not in the spanning tree, we get n-1+1=n. This violates the property of CAG which implies that the graph has a cycle.
b)by part a, we have n vertices and n different edges, so if we take away 1, we will have n-1 different edges which implies that the graph is acyclic.