2 votes 2 votes The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________. Graph Theory gatecse2024-set1 numerical-answers graph-theory graph-connectivity + – Arjun asked Feb 16 • retagged Apr 26 by Arjun Arjun 2.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply ritiksri8 commented Mar 26 reply Follow Share apply cayley formula 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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.$ Hira Thakur answered Feb 16 Hira Thakur comment Share Follow See all 2 Comments See all 2 2 Comments reply GauravRajpurohit commented Feb 18 reply Follow Share 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? 0 votes 0 votes Raizel commented Feb 21 reply Follow Share 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 nC2 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 : 6C3 = 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. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes Ans. Number of spanning trees in complete graph can be given by cayley formula:- nn-2 i.e. 44-2=42=16. ritiksri8 answered Mar 20 ritiksri8 comment Share Follow See all 0 reply Please log in or register to add a comment.