# Homework Help: Easy proof about spanning trees (for you)

1. Nov 24, 2015

### TheMathNoob

1. The problem statement, all variables and given/known data
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 any one 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

2. Relevant 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".

3. 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.

2. Nov 24, 2015

### andrewkirk

Let G' be G with the edge wi,wi+1 removed.
Pick any vertex x in G. Divide the vertices of G into subsets A(x) and B(x) where vertices in A(x) can be reached from x via G' and vertices in B(x) cannot.
Pick a vertex y in B(x). Now all you need to do to prove (b) is to demonstrate a route from x to y in G2.

Last edited: Nov 25, 2015
3. Nov 24, 2015

### TheMathNoob

Hi andrewirk, thank you so much for helping me out. What is v?

4. Nov 24, 2015

### andrewkirk

That should be x. I started with u and v, then changed them to x and y when I saw that you'd already used those letters for edges. It looks like I missed one when I was changing over.

5. Nov 25, 2015

### TheMathNoob

wh
what is G2?

6. Nov 25, 2015

### andrewkirk

It's what you defined it as in (b) of the OP