Tee Jet Whaw

Suppose you have 2 vertices (points) – 1 red and 1 blue – how many ways can you join them together? There’s only way to do it, which is to draw a line between the 2 points.

Now, what if you have 3 vertices – 1 red, 1 blue and 1 green – how many ways can you join these all together?

Let’s start by drawing 2 lines as shown below:

Here we see that red and blue are joined, and red and green are joined. So, we can move the points around and create a different graph – for example joining red and green, and green and blue to get a different tree:

There is one final way to arrange the graph, that is blue joining to green and blue joining to red, which gives a total of 3 different trees that can be made from 3 labelled (meaning differently coloured) vertices.

For 4 and beyond, things get a little trickier. Have a go for yourself and see how many trees you can create using 4 different vertices (red, blue, green and yellow). And if you’re up for a real challenge, try to come up with a formula for the number of tress that can be made from n labelled vertices.

Scroll down for the answer!

.

.

.

.

.

.

.

.

.

.

After a little bit of thought, you will hopefully see that there are in fact 16 different trees – 12 which have the points joined in a loop (in different orders as with the case of 3 points), and a further 4 that can be formed by using a central point (4 choices as they are 4 different colours).

For the general case of n vertices, there are a total of n^n-2 different trees that can be made. You can check this result for the above cases with n = 2, n^n-2 = 2⁰ = 1. For n = 3, n^n-2 = 3¹ = 3 and for n = 4, n^n-2 = 4² = 16.

There are many ways to prove the general result – known as Cayley’s Formula – and here is one example using double counting (don’t worry if you can’t follow all of the steps, this is quite advanced!): 

To start, suppose there are F(n) undirected trees (this is what we want to know). We can then produce directed trees with numbered edges (meaning the order in which you traverse the graph is given) as follows:

Step 1: For each undirected tree, choose a root (starting point) so that the tree automatically becomes directed. There are n choices for this root (since we have n points).

Step 2: Number the (n-1) edges (if there are n vertices which are all connected as a tree then we know there are (n-1) of them – you can check this with our examples above for small n). There are (n-1)! ways to do this numbering.

Therefore, in total we have F(n) x n x (n-1)! = F(n) x n! directed trees with numbered edges that can be constructed out of n points.

Meanwhile, we can also produce a directed tree with numbered edges by adding edges to n separate vertices:

1. Note that if we’ve added k edges to the empty graph, we’re left with (n-k) trees since adding an edge decreases the number of trees by 1 (as two of the original number must now be joined).
2. When we add an edge each time, we can choose any of the points to be our starting point, and the root of any other tree to be our end point. This gives n starting points and (n-k-1) end points to choose from each time.

Overall, cycling through the values of k from 0 to n-1 we therefore have (n(n-1)) x … x (n(1)) = n^n-1 x (n-1)! = n^(n-2) x n! directed trees with numbered edges.

Since both methods are counting the same thing (the number of directed tress with numbered edges) we can equate the formulas to get F(n) x n! = n^n-2 x n! and so F(n) = n^(n-2).