1
00:00:00,000 --> 00:00:06,566
In this short video, we’ll be looking at an elegant proof of Cayley’s formula about the number of spanning trees in a complete graph.
2
00:00:07,233 --> 00:00:12,233
It was discovered by Jim Pitman, and is a great example of a powerful proof technique called double counting.
3
00:00:14,733 --> 00:00:21,599
A complete graph on n vertices (denoted Kn ) is a graph, where each pair of vertices is connected by an edge.
4
00:00:22,750 --> 00:00:29,116
A spanning tree in a graph is a subgraph that is a tree and includes all vertices of the original graph.
5
00:00:29,116 --> 00:00:33,166
A good way to think of it is that it’s the smallest subgraph that keeps the graph connected.
6
00:00:35,683 --> 00:00:38,033
Cayley’s formula is rather simple.
7
00:00:38,033 --> 00:00:44,449
It states that the number of spanning trees of a complete graph on n vertices is κ(n) = n^(n−2).
8
00:00:45,383 --> 00:00:48,966
While being simple in statement, it’s definitely not trivial to prove.
9
00:00:49,616 --> 00:00:53,566
Also, it is worth noting that these three spanning trees are different.
10
00:00:54,133 --> 00:01:01,233
Although they are the same in structure (the fancy term here is isomorphic), they differ in where the edges actually are, which is what matters.
11
00:01:02,983 --> 00:01:07,450
As I’ve mentioned earlier, the proof technique that we’ll be using is double counting.
12
00:01:07,450 --> 00:01:12,183
This involves, as the name suggests, counting some quantity in two different ways.
13
00:01:13,333 --> 00:01:20,383
For this proof, we’ll be counting the number of oriented trees on n vertices that have a root and some numbering of edges.
14
00:01:20,383 --> 00:01:21,683
Let’s call this quantity τ(n).
15
00:01:23,400 --> 00:01:26,033
Here are two examples of what the trees could look like.
16
00:01:30,416 --> 00:01:34,933
First, let’s just count the number of trees without root and edge numbering.
17
00:01:34,933 --> 00:01:37,816
This, from definition, equals κ(n).
18
00:01:38,750 --> 00:01:41,634
Next, the root can be any of the n vertices
19
00:01:43,750 --> 00:01:45,000
so we multiply by n.
20
00:01:46,283 --> 00:01:52,599
Finally, the edge numbers can be any permutation of numbers from 0 to the number of edges, which is n − 1.
21
00:01:53,700 --> 00:01:58,700
This brings the total to κ(n) ⋅ n ⋅ (n − 1)!
22
00:02:00,350 --> 00:02:06,033
The other way will be constructive – we’ll build the tree by adding oriented edges between the vertices,
23
00:02:06,033 --> 00:02:07,899
with numbers depending on when they were added.
24
00:02:09,333 --> 00:02:13,949
Looking at the example graph, we can make two observations about the edge we’re about to add.
25
00:02:14,466 --> 00:02:19,466
1. it has to start in the root of a component, because otherwise some edges wouldn’t be pointing towards the root
26
00:02:21,000 --> 00:02:26,733
2. it can not be between two vertices of a single component, as this would create a cycle, which a tree can not have
27
00:02:28,183 --> 00:02:34,199
Putting this together, let’s count the number of ways we can add the k-th edge (counting from zero).
28
00:02:34,200 --> 00:02:36,200
In our example, k = 3.
29
00:02:37,966 --> 00:02:41,033
The edge can end in any vertex, of which there are n.
30
00:02:42,616 --> 00:02:48,583
Given this end, we know it has to start from the root of some component (observation 1)
31
00:02:48,583 --> 00:02:51,883
and it can not start in the component where it ends (observation 2).
32
00:02:52,950 --> 00:03:00,684
This means that from the n − k components that we currently have, it can only start in n − k − 1 of them, since one is reserved for the end.
33
00:03:02,366 --> 00:03:06,083
To build the entire tree, all n − 1 edges must be added.
34
00:03:07,100 --> 00:03:14,216
When adding the k-th edge, there are n ⋅ (n − k − 1) ways to do so, resulting in the following formula.
35
00:03:15,233 --> 00:03:19,166
Here, we can take the n out, becoming n^(n−1).
36
00:03:20,066 --> 00:03:29,249
As for the product itself, notice that this is just (n − 1) ⋅ (n − 2) ⋅ ... ⋅ 1, which equals (n − 1)!
37
00:03:30,450 --> 00:03:35,450
Using the previous way to count, we can simplify, divide by n and we’re done.