How many labelled spanning trees does the complete graph K7 have?
Answer and explanation
Correct answer: B. 16807
- Step 1: Cayley's formula gives n^(n−2) labelled trees on n vertices. Step 2. 7^5 = 16807. Answer: 16807. Why not the others: 117649 is what you get if you use n^(n−1). 720 is what you get if you use (n−1)!. 21 is what you get if you give the number of edges.
Practise more Linear algebra, calculus and probability.
Free questions with an explanation for every one, and full timed GATE mock tests.
More Linear algebra, calculus and probability questions
- What is the rank of the matrix with rows (3, 6, 9); (6, 12, 18); (9, 18, 27)?
- If P(A and B) = 0.05 and P(B) = 0.5, what is P(A given B)?
- Find the divergence of F = (x², y², z²) at the point (1, 2, 2).
- The solution of dy/dx = −6y with y(0) = 6 is
- How many functions are there from a set of 5 elements to a set of 6 elements?
- A 2×2 matrix has eigenvalues 4 and -4. What are the trace and determinant?