1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Easy proof about spanning trees (for you)

  1. Nov 24, 2015 #1
    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. jcsd
  3. Nov 24, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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
  4. Nov 24, 2015 #3
    Hi andrewirk, thank you so much for helping me out. What is v?
     
  5. Nov 24, 2015 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Nov 25, 2015 #5
    wh
    what is G2?
     
  7. Nov 25, 2015 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's what you defined it as in (b) of the OP
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted