Arrange the following graph on the basis of number of edges in increasing…
2025
Arrange the following graph on the basis of number of edges in increasing order [for n > 3]
A. Kₙ (Complete Graph)
B. Cₙ (Cycle graph)
C. Wₙ (Wheel graph)
D. Kₘ,ₙ (Complete Bipartite Graphs)
E. Qₙ (n-cubes graph)
Choose the correct answer from the options given below:
- A.
A, B, C, D, E
- B.
B, A, C, D, E
- C.
A, B, C, E, D
- D.
E, D, C, A, B
Attempted by 171 students.
Show answer & explanation
Correct answer: B
Assumptions: compare graphs having the same total number of vertices n>3. For the complete bipartite graph Kₘ,ₙ we take the usual comparison where the two partition sizes sum to the same total number of vertices (so m + n = total vertices); when needed we consider the balanced case ⌊n/2⌋,⌈n/2⌉ to maximize edges in the bipartite family.
Cycle Cₙ: n edges.
Wheel Wₙ: 2(n−1) edges (a cycle on n−1 vertices plus n−1 spokes).
Complete bipartite Kₘ,ₙ (with partitions summing to n): m·n edges; for fixed total vertices this is at most ⌊n²/4⌋, achieved when the partition is as balanced as possible.
Complete graph Kₙ: n(n−1)/2 edges.
n-cube Qₙ: n·2^{n−1} edges (grows exponentially in n).
Compare these formulas:
For all n>3, the cycle has the fewest edges: Cₙ (n) < Wₙ (2(n−1)) for n>2.
The relative order of Wₙ and Kₘ,ₙ depends on n and the partition sizes, but for the balanced bipartite case compare 2(n−1) with ⌊n²/4⌋.
Always Kₘ,ₙ (with partitions summing to n) has at most ⌊n²/4⌋ edges, which is strictly less than n(n−1)/2 for n>3; hence Kₘ,ₙ < Kₙ.
The n-cube Qₙ has far more edges than the others for n>3, so it should be last in the increasing order.
Concrete small-n checks (examples):
n = 4: counts → C₄=4, W₄=6, balanced Kₘ,ₙ=4, K₄=6, Q₄=32. One increasing order by value is C₄ = K₍balanced₎ (4) < W₄ = K₄ (6) < Q₄ (32).
n = 5: counts → C₅=5, W₅=8, balanced K₍2,3₎=6, K₅=10, Q₅=80. Increasing order: C₅ (5) < K₍2,3₎ (6) < W₅ (8) < K₅ (10) < Q₅ (80).
n ≥ 7: numeric comparison shows Cₙ < Wₙ < K₍balanced₎ < Kₙ < Qₙ (the balanced complete bipartite overtakes the wheel when n is large enough).
Final conclusion: the question as stated is ambiguous because Kₘ,ₙ is not fully specified. Under the standard interpretation that all graphs have the same number of vertices and comparing the balanced complete bipartite case, the increasing-edge order for typical n (and certainly for all sufficiently large n) is: Cₙ, Wₙ, K₍⌊n/2⌋,⌈n/2⌉₎, Kₙ, Qₙ. For small n some tie or swap cases occur (examples shown above).
Therefore the original key (which gave the order "Cₙ, Kₙ, Wₙ, Kₘ,ₙ, Qₙ") is not generally correct; the improved, clearly explained ordering is provided above along with the assumptions and small-n checks.
A video solution is available for this question — log in and enroll to watch it.