Normal spanning trees and swirl cupcakes

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.

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 fix a vertex called the root, r, of the tree. Next, we define a partial order on the vertex set of G by 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 , 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:

Place a teaspoon of each frosting on the cupcakes like this

Use the tip of a butterknife to swirl the colours into each other

A closeup of the result

Christmas brownies

It would seem I have lapsed in my blogging. But, this time I’m making up for it with a recipe for Christmas brownies. My first semester of grad school is over (at least until the grades are released) and I decided it called for brownies. Then I had some more realisations: it is almost Christmas, and the best part of Christmas is peppermint mochas. So I decided to modify my tried and true briwnie recipe into peppermint mocha brownies. I also decided that these brownies needed a little extra in the form of spiced rum. As always with brownies, you need to use a good quality chocolate that you enjoy eating on its own, as this is what your brownies will taste like. I used Ghiradelli’s 70% cocoa chocolate chips for mine, and it turned out delicious.

Ingredients for brownie:

• 4oz dark chocolate
• 1/2 cup butter
• 2 tsp instant coffee
• 1/2 tsp peppermint extract
• 2 tbsp dark, spiced rum
• 3/4 cup granulated sugar
• 2 eggs
• 3/4 cup flour

Ingredients for topping:

• 4oz dark chocolate
• 2tbsp heavy cream
• 1 candy cane, crushed

Preheat the oven to 325 degrees Fahrenheit. Melt the chocolate and butter in a pot over low heat. Stir carefully to make sure it doesn’t burn (if you are worried, melt it in a steel bowl over a water bath). Take the pan off the heat and stir in the instant coffee, peppermint extract and rum. Add in the sugar, and then the eggs, mixing carefully after each addition. Finally add in the flour. Pour the batter into a 9×9 inch brownie pan and bake for 20-25 minutes or until a toothpick inserted in the center comes out with a few moist crumbs. Closer to 20 minutes will yield a more fudge-like brownie, and closer to 25 will give you a more cake-like one. Let the brownie cool completely before attempting to decorate it.

When it is cooled, melt the dark chocolate (on the stove or in the microwave) and stir in the heavy cream. Spread this over the brownie, sprinkle the crushed candy cane over it and then chill for about an hour. Cut into 9-16 pieces, depending on how big you like your brownies (the correct answer is as big as possible without getting sick from too much sugar). Serve room temperature or cold, possibly with some vanilla ice cream or whipped cream.

I didn’t realise how much a crushed candy cane sprinkled over the chocolate topping would add to the cake until after I took the pictures: hence the lack of red and white sprinkles there.

These are the perfect thing to enjoy on a rainy December evening with a good book. They are dense, chocolatey and with a certain oomph from the rum, coffee and peppermint. I’m currently obsessed with Ken Follett, and if my grad student budget allowed me to I would have bought all of his books as a Christmas present to myself. As it stands I have to ration them a little. But now I’m off to find any brownies my roommate and boyfriend haven’t eaten and finish Winter of the World. Enjoy your brownies!

Simple Birthday Cake

For my birthday a few days ago (finally 21!), I made a delicious cake, featuring some of my current favorite tastes. The first layer is a brownie like cake, covered in a very tart lime mousse, and then with a pile of strawberries on top. This cake takes a little while to make, mostly because everything has to cool and set in between layers. It’s very simple though, as long as you’re gentle with the mousse. It would be a good idea to make the brownie cake the night before and the mousse in the morning.

For the brownie cake you will need:

• 100 grams butter
• 4 tablespoons cocoa powder
• 1 pinch of salt
• 1 teaspoon vanilla extract
• 3 deciliters granulated sugar
• 1.5 deciliters flour
• 2 eggs

Set the oven to 160 degrees Celsius. Melt the butter. While it cools slightly, mix all the dry ingredients in a large bowl. Stir in the eggs one by one and then the butter. Transfer to a buttered springform pan (24 – 28 cm diameter), dusted with cocoa powder, and bake for approximately 35 minutes. A toothpick inserted in the center should still be sticky. This cake needs to cool completely before the next step. I would recommend removing the edge of the springform pan and cleaning it before making the mousse, to end up with a nice, clean cake.

The mousse is a little bit harder to make, but still fairly simple. You will need:

• 2 gelatin leaves
• 2 deciliters heavy cream
• 2 eggs, separated
• The juice of 3 limes
• 3/4 deciliter granulated sugar

Soak the gelatin leaves in cold water. Whip the cream until soft peaks form. Gently fold the egg yolks into the cream. In a separate bowl, whip the egg whites until hard peaks form. Heat up the lime juice mixed with the sugar, but don’t let it boil. Stir the gelatin leaves into the lime juice. Fold the lime mixture into the whipped cream. Finally, fold in the egg whites, a little at a time, very gently. Spread this mixture on the cake and let it set in the fridge for at least 3 hours.

• 2 cups of sliced strawberries
• (Powdered sugar)

To serve, cover the top with sliced strawberries and (depending on how sweet they are) dust some powdered sugar over the cake. Enjoy!