Results 1 to 5 of 5

Math Help - Every connected graph contains a maximal tree

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    16

    Every connected graph contains a maximal tree

    Hi

    I'm looking at a proof that every connected graph G contains a maximal tree T (that is, a tree such that for any edge e in G, T(union)e is no longer a tree).

    The proof begins by enumerating the (possibly countably infinite) vertices of G.

    The proof then asserts that we may assume that for any i>=2, the ith vertex shares an edge with a jth vertex where j<i.

    This seems intuitive but I can't see exactly how we could ensure that this is the case.

    Any help with seeing why we may assume this would be a great help. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433

    Re: Every connected graph contains a maximal tree

    The manner in which the vertices are enumerated is important. I'm guessing you started with an arbitrary vertex and called it v_0, then repeated the following step--for every vertex that's not already in the list, and which shares an edge with a vertex that is in the list, add it to the end of the list--until every vertex is in the list, which is guaranteed to happen eventually (possibly after infinitely many steps, but countably infinitely many, so that the number of vertices already in the list at any given step is finite) by connectedness of the graph.

    Clearly every vertex was added at some step, and was added because it shared an edge with a vertex already in the list, i.e. a vertex with lower index.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    16

    Re: Every connected graph contains a maximal tree

    Thanks for the reply. I still have a problem with this though:

    What if there are countably infinitely many vertices attached to v_0?

    Surely then this method fails?

    Thanks in advance for any help!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433

    Re: Every connected graph contains a maximal tree

    Hmm, you're right. There are no conditions on the graph other than that it's connected and has at most countably many vertices? Well, this seems rather complicated for a "we may assume" step, but you could index the neighbors of v_0 as 2,2^2,2^3,2^4,\dots, and the neighbors of v_{2^k} as 2^k3,2^k3^2,2^k3^3,\dots, and so on (where we use the i^{th} prime number at the i^{th} step. Of course, when there's a cycle you end up assigning infinitely many indices to the vertices in that cycle, but you can just take the lowest one.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2011
    Posts
    16

    Re: Every connected graph contains a maximal tree

    got it.

    great thanks a lot!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  2. Replies: 6
    Last Post: November 12th 2010, 07:03 AM
  3. k-connected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2010, 04:26 PM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. graph + tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 4th 2010, 11:27 PM

Search Tags


/mathhelpforum @mathhelpforum