Consider the Graph below:
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 K₄ with one edge missing (5 edges on 4 vertices). K₄ has 16 spanning trees and each edge lies in 16 × 3/6 = 8 of them, so removing one edge leaves 16 − 8 = 8.
More Discrete Structures and Optimization questions
- Match the List-I and List-II
- Four persons: P, Q, R and S are in police custody and one of them has committed a crime. They confess as follows: A. Person P: Q did it. B.…
- Consider the primal problem: maximize z = 5x1 + 12x2 + 4x3 subject to x1 + 2x2 + x3 = 10, 2x1 − x2 + 3x3 = 8, x1, x2, x3 ≥ 0. Its dual is:…
- Considering α, β, γ as logical variables, which represent correct equivalences? (A) (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) (B) (α ∨ β) ≡ ¬α ∨…
- Let ({a, b}, *) be a semigroup where a * a = b. Which hold? (A) a * b = b * a (B) b * b = b
- Let ε = 0.0005 and R_ε be the relation {(x, y) ∈ ℝ² : |x − y| < ε}, interpreted as 'approximately equal'. R_ε is (A) reflexive (B) symmetri…