Extra material : Day 10

The extra stuff today consists of a few remarks about counting trees.

Definition : Let G_{1}, G_{2} be simple graphs. An isomorphism from G_{1} to G_{2} is a bijection

ϕ : V (G_{1}) → V (G_{2})

such that, for any two vertices v, w of G_{1}, {v, w} is an edge in G_{1} if and only if {ϕ(v), ϕ(w)} is an edge in G_{2}.

If there exists such an isomorphism we say that G_{1} is isomorphic to G_{2}. It’s an easy exercise to check that ‘being isomorphic to’ is an equivalence relation on graphs, and hence we can talk about isomorphism classes of graphs. Informally, two graphs are isomorphic if they have the same number, say n, of vertices, and you can label the vertices of each graph from 1 to n in such a way that the two graphs then have the same edges.

Remark 1 : As far as I know, no nice formula exists for the number of isomorphism classes of simple graphs on n vertices. In fact, even if we restrict our attention to trees, there is no such formula. This is maybe not surprising given the next remark -

Remark 2 : The graph isomorphism problem is the algorithmic problem of deciding whether two arbitrarily given graphs are isomorphic. I believe the current status of this problem is that it is in NP (i.e.: no polynomialtime algorithm is known), but it is an open question as to whether it is NP-complete. As such, it has a similar status to the integer factorisation problem.

Definition : Let n > 0. A labelled graph on n vertices is a pair (G, α), where G is a graph on n vertices and α is a bijection from V (G) to {1, ..., n}. For obvious reasons, the map α is called the labelling of the graph G.

Definition : Two labelled, simple graphs (G_{1}, α_{1}) and (G_{2}, α_{2}) are said to be isomorphic (as labelled graphs) if they have the same number, say n, of vertices, and the map

α_{2}^{−1} ∘ α_{1} : V (G_{1}) → V (G_{2})

is an isomorphism of (ordinary) graphs.

If we restrict our attention to trees, then this time there is the following surprisingly simple fact :

Theorem (Cayley) The number of isomorphism classes of labelled trees on n vertices is n^{n−2}.

I don’t know of any ‘really’ simple proof of this theorem. The book ‘A Course in Combinatorics’ by J.H. van Lint and R.M. Wilson has three proofs !!

I also made a remark in class to the effect that the number of ‘plane rooted trees’ on n vertices is just the Catalan number C_{n−1}. Here we are distinguishing between any two trees which only differ by a symmetry of the plane. There is an explicit 1-1 correspondence between such trees on n vertices and Dyck paths of length 2n − 2, namely : take a walk around the tree, from ‘left to right’, starting and finishing at the root. Since there are n − 1 edges and each edge is passed over twice, your walk consists of 2n − 2 steps. The corresponding Dyck path has an up-step (resp. down-step) for every step in your walk which takes you further away from (resp. nearer) the root. The path hits the x-axis every time you arrive back at the root during your walk.