Easy proof about spanning trees (for you)

[TheMathNoob]

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.

 

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

 

[TheMathNoob]

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

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

 

[andrewkirk]

What is v?

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.

 

[TheMathNoob]

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.

wh

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.

what is G2?

 

[andrewkirk]

what is G2?

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