Consider the following graph with vertices A, B, C, D and edges:
A – B, B – C, A – D, B – D, C – D
(A, B, C lie in a row; D is below and joined to all three.)
How many spanning trees can be found?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. 8
Explanation
The graph is K4 minus the edge A–C. K4 has 42 = 16 spanning trees and each edge lies in 16 × 3/6 = 8 of them, so 16 − 8 = 8 trees avoid A–C.More Discrete Structures and Optimisation questions
- Consider the following statements: P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges. Q: All vertices…
- Consider the following statements: A. There exists a Boolean algebra with 5 elements. B. Every element of a Boolean algebra has a unique co…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Planar graph I. Probabilistic model b.…
- Consider the statements: I. There does not exist a polynomial-time algorithm to solve integer linear programming problems. II. The main foc…
- Four persons P, Q, R and S are in custody and one of them has committed a crime. They say: P: Q did it. Q: S did it. R: I did not do it. S:…
- There are three boxes. The first box has 2 white, 3 black and 4 red balls. The second box has 3 white, 2 black and 2 red balls. The third b…