Normal spanning trees and swirl cupcakes

by aajohannas

Today I had my last official class of my first year, a topology class. We talked about homology invariants and ate the chocolate vanilla swirl cupcakes I made for the occasion. It’s weird that I don’t have any more classes left. I almost even miss analysis homeworks. I have plenty of things to keep myself occupied until August though. Tomorrow I have a mandatory research ethics course to attend. 8 hours of listening to someone talk about how we shouldn’t experiment on people without the permission of the ethics review board. I imagine it will be moderately interesting, at best. Well, unless I come up with some experiment like these two mathematicians, courtesy of Spiked Math.

Animal testing

Today I want to share some interesting graph theory. Given a connected graph G, we can find a spanning tree T. This can be proved by simple induction. However, it is also true that we can find a normal spanning tree in any connected graph.

Given a tree T fix a vertex called the root, r, of the tree. Next, we define a partial order on the vertex set of G by x \leq y if x is in the unique path from r to y. This is the partial tree-order associated with r.

We call a rooted tree with root r normal in G if every pair of vertices that are adjacent in G is comparable in the tree-order associated with r.

Theorem. Every connected graph G has a normal spanning tree.

The reason I wanted to share this result with you is because it has a beautiful inductive proof where we induct on the number of edges. Think about it for a few minues before you scroll down to see.

Proof. For the base case, consider a connected graph on one edge. Clearly, this graph is K_2, which is its own normal spanning tree. Now suppose every graph on n edges has a normal spanning tree. Then there are three cases for the inductive step: if we add another vertex, then the new normal spanning tree will be the old one joined with the new edge. Since there are no more edges connected to the new edge, this is still a normal spanning tree.

In the second case, we add the new edge to the old graph, but it does not affect the partial order on the normal spanning tree, so we are done.

The final case is the tricky one: suppose that the new edge connects two vertices that are not comparable in the tree order. In this case, we create a new spanning tree by adding in the new edge, connecting two branches of the spanning tree. Then we pick one of the original branches and delete the edge in it closest to the root of the tree. Then we have a spanning tree again, and it is normal. Q.E.D.

Oh, and those cupcakes I mentioned? I used a recipe I found on JoyOfBaking. This is one of the best sites I have ever found for basic recipes, like vanilla cupcakes, brownies, red velvet cake, peanut butter cookies, and so on. I highly recommend it. I separated the frosting in two bowls, melted a handful of dark chocolate chips and whipped into one of them to make half chocolate and half vanilla frosting. And here’s the end result: