GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
781 views

The number of spanning trees for a complete graph with seven vertices is

  1. $2^5$
  2. $7^5$
  3. $3^5$
  4. $2^{2 \times 5}$
asked in Algorithms by Veteran (13.7k points)   | 781 views

4 Answers

+12 votes
Best answer

No of spanning tree possible in complete graph with n node=nn-2 

So No of spanning tree possible in complete graph with 7 node=75

spanning tree possible in complete graph

answered by Veteran (36.3k points)  
selected by
correct
+1 vote

Number of spanning tree in complete graph have k vertex==K^K-2

Ex::

K=7

No. of spanning tree possible is=7^7-2=7^5

Option B will be right option

answered by Loyal (4.6k points)  
0 votes

The number of spanning trees in the complete graph Kn is nn-2

answered by Loyal (4.6k points)  
0 votes
Number of Spanning trees in Complete Graph of N vertices = N^(N-2)

According to Question:

N=7

So number of spanning trees will be = 7^(7-2)

                                                     = 7 ^ 5
answered by Loyal (4.3k points)  


Top Users Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users