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:
One theorem that I constantly run into (mainly because it’s relevant to homology) is the following:
Theorem. Given some connected finite graph , there exists a spanning tree of .
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 . If has no cycles then it is, itself, a tree; hence, is its own spanning tree. Suppose now that any graph with cycles has a maximum spanning tree. Given some graph with 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.
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!