Thread: 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!

The manner in which the vertices are enumerated is important. I'm guessing you started with an arbitrary vertex and called it , 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.

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!

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 as , and the neighbors of as , and so on (where we use the prime number at the 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.

got it.

great thanks a lot!