Existence of Spanning Trees in Finite Connected Graphs.

March 5, 2012

[Note: It’s been too long, mathblog!  I’ve been busy at school, but I have no plans to discontinue writing in this thing.  For longer posts, you’ll have to wait until I have some free time!]

 

You’ve probably seen a graph before: they’re collections of vertices and edges pieced together in some nice way.  Here’s some nice examples from wikipedia:

File:McGee graph.svg

File:Moser spindle.svg

 

 

One theorem that I constantly run into (mainly because it’s relevant to homology) is the following:

 

Theorem.  Given some connected finite graph G, there exists a spanning tree of G.

 

Note that such a tree is not generally unique.  You might want to find one or two in the graphs above to prove this to yourself!  Nonetheless, even though this proof seems like it would be a bit intimidating (or, at least, by some sort of tedious construction), it’s actually quite nice.  Let’s go through it.

 

Proof. We’ll prove this by the number of cycles in G.  If G has no cycles then it is, itself, a tree; hence, G is its own spanning tree.  Suppose now that any graph with n cycles has a maximum spanning tree.  Given some graph with n+1 cycles, take any one of these cycles and delete any edge (but not deleting the vertices!).  This reduces the number of cycles by (at least) one, so there is a spanning tree by induction.  In fact, since we have not deleted any vertices, we may replace the edge we removed and this tree will still span the graph.  \Box

 

A couple of questions about this for the eager reader.  Where did we use connectedness?  Where did we use finite-ness?  What if we were given an infinite graph?  Is there a nice notion of cycles for this kind of graph?  Draw some pictures and think about it!

Advertisements

2 Responses to “Existence of Spanning Trees in Finite Connected Graphs.”

  1. This proof constructs a spanning tree from the outside in (deleting edges until you get a spanning tree), which doesn’t seem to generalize well to infinite graphs. The proof I know goes from the inside out (adding edges until you get a spanning tree) and generalizes immediately.

    Pick a connected (not necessarily finite) graph. Once you show that the union of an increasing chain of subgraphs which are trees is also a tree, it follows by Zorn’s lemma that there exists a maximal subgraph which is a tree. If this tree isn’t a spanning tree, then some vertex not contained in it is adjacent to a vertex that is (by connectedness), and adding that edge creates no cycles; contradiction.

    • James said

      Oh! I like that proof. I hadn’t even thought of using Zorn that way. The proof above was to help along some students in an undergrad level topology course where (I don’t think!) they’d been introduced to Zorn yet. Nonetheless, it’s a pretty accessible result; thank you!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: