# Every connected graph contains a maximal tree

• Oct 4th 2011, 04:56 AM
oOoOo
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!
• Oct 4th 2011, 06:08 AM
Tinyboss
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.
• Oct 4th 2011, 07:11 AM
oOoOo
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!
• Oct 4th 2011, 07:38 AM
Tinyboss
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.
• Oct 4th 2011, 07:44 AM
oOoOo
Re: Every connected graph contains a maximal tree
got it.

great thanks a lot!