Cayley’s Theorem: Enumeration of Graphs

Hello Readers,

Hope you all are doing well.

Today, I am going to write the proof of Cayley’s Theorem which counts the number of labelled trees. Cayley’s Theorem is very important topic in graph theory. If you study Graph theory and don’t know Cayley’s theorem then it would be very surprising.

Ok, So lets start having a look on some terminologies:

Tree: A connected graph without any cycle.

Prufer Sequence:  A sequence S of length n-2 defined on n elements is called Prufer sequence. It was used to prove Cayley’s theorem.

Prufer sequence of a labelled tree is unique sequence associated with that tree.z

Labelled Tree:  A tree in which each vertex is assigned a unique name or label (i.e no two vertices have the same label) is called a labelled tree.

Traditionally, the vertices of a tree are labelled by integers 1,2,3,……,n where n is the number of vertices in tree.

So, we can arise a natural question,

How many labelled trees are there with n number of vertices?

Cayley’s formula for enumeration of Graphs gives the answer of this question.

Lets discuss the proof of Cayley’s Theorem in easy way as follows:

Cayley’s Theorem:  There are n^(n-2) labelled trees with n vertices.

Proof: Basic idea of this proof is to show that a labelled tree T has one to one correspondence with Prufer sequence. If yes then ofcourse number of labelled trees is equal to number of Prufer sequences.

Now find how many such Prufer sequences on n elements of length n-2?

To find it, let us take n-2 boxes.

Each box can be filled with any of n elements. So for each box, there are n possibilities.

Thus, total number of such Prufer sequences = n× n× n× n×……….×n (n times)

= n^(n-2)

So number of labelled trees on n vertices  =  n^(n-2) if there exist one to one correspondence between labelled tree with n vertices and Prufer sequence on n elements.

So only thing is now to prove that Labelled tree⇔ Prufer sequence

One way: Given a labelled tree on n vertices, determine uniquely a Prufer sequence on n elements.

Follow the following algorithm:

Step 1. Find a pendant vertex say v of T with smallest label

Add the adjacent vertex of v to S and delete the pendant vertex from T.

Step 2. Repeat step 1 until our tree T is K_2.



Converse: Given a Prufer sequence on n elements, determine uniquely a labelled tree on n vertices.

Let S be a Prufer sequence of length n-2 using n elements so take S={b1,b2,b3,….b(n-2)}, where each bi∈ L={1,2,3,…..n}.

now follow the following algorithm :

Step 1. Find the smallest element x∈L which is not in S.

Join x to the Ist element of S s.t. (x, b1) is an edge.

Delete b1 from S and delete x from L and update S and L.

Step 2.  Repeat step 1 untill 2 elements remain in L.

Step 3. Finally join these two remaining vertices in L via an edge.




Hope you really understood.

Stay Connected, Stay learnt

Thank you

Dr. Namita Tiwari




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s