Arrange the following simple graphs by the number of spanning trees they have (increasing):
A. K₃ (complete graph on 3 nodes)
B. K₄ (complete graph on 4 nodes)
C. K₂,₂ (complete bipartite graph with 2 nodes in each part)
D. C₅ (cycle graph on 5 nodes)
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. A, C, D, B
Explanation
By Cayley, K₃ has 3 and K₄ has 4² = 16. K₂,₂ is the 4-cycle with 4, and C₅ has 5. Increasing: A, C, D, B.More Discrete Structures and Optimisation questions
- A bit string of length four is generated at random. What is the probability that it contains at least two consecutive 0s, given that the fi…
- Arrange the following sets in increasing order of their cardinality: A. A1 = {{1, 2}, {3}} B. A2 = {{1}, {2}, {3}, {4}} C. A3 = {{1, 2, 3,…
- The chairs of an auditorium are to be labelled with a letter followed by a positive two-digit integer, starting with A01. What is the maxim…
- Z is the set of integers. ⟨Z, *⟩ forms a group if * is:
- Arrange the steps of mathematical modelling: A. Solution fitting with data B. Formulation mathematically C. Solve mathematically D. Repeat…
- Which of the following are tautologies? A. (p ∨ r) → p B. p → (p ∧ r) C. ~p → (p → r) D. (p ∧ r) → (p → r) E. ~(p → r) → p Choose the corre…