GATE CSE 2024 | Set 1 | Question: 24

Question

The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.

Answer 1

Number of spanning trees in any complete graph $(K_n)$ is $n^{n-2}$, where $n$ is a number of vertices.

here $n=4\therefore $ the number of spanning tree is $4^{4-2}=4^2=16$

So the correct answer is $16.$

Comments

I don't know where was I wrong in this question but during the exam, I drew a complete graph on 4 vertices, and then I thought it is a complete graph so if chose any vertices at first then I got tree so in that way for selecting first node I have 4 choices and similarly for selecting second third and last node I have 3, 2, 1 respectively choices so I will get 4! as my answer but I don't know where my thinking is wrong please help me, sir. Where I had done overcounting?

---

First, read the question carefully. Don't forget it's a Tree,  and the Spanning Tree must have n-1 edges. In a complete graph of n vertices, you have max ⁿC₂ edges. So here total edges = 6. 

In a spanning tree you need n-1 edges, so here it should 4-1 = 3edges. 
Now, out of total 6 edges, in how many ways can you select 3 edges : ⁶C₃ = 20.

Out of 20 ways, how many actually form cycles (3 length cycles)? = 4. (you can even check it manually, each diagonal contribute to two triangles).
So remaining = 20-4 = 16 answer.

Answer 2

Ans. Number of spanning trees in complete graph can be given by cayley formula:- n^n-2 

i.e. 4^4-2=4²=16.