Arrange the following graphs on the basis of number of edges in increasing order (for large n):
A. Kₙ (Complete Graph)
B. Cₙ (Cycle graph)
C. Wₙ (Wheel graph)
D. Kₙ,ₙ (Complete Bipartite Graph)
E. Qₙ (n-cube graph)
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: B. B, C, A, D, E
Explanation
Edges: Cₙ = n, Wₙ = 2n, Kₙ = n(n−1)/2, Kₙ,ₙ = n², Qₙ = n·2ⁿ⁻¹. For larger n (n ≥ 6, e.g. 6 < 12 < 15 < 36 < 192) the order is B, C, A, D, E.More Discrete Structures and Optimization questions
- A linear programming problem (LPP) is as follows: Min z = 30x − 18y, subject to the constraints 3x + 4y ≤ 60, 5x − 3y ≥ 20 and x, y ≥ 0. In…
- Which of the following graphs is/are planar? Graph A (vertices a–f): edges ab, ac, bd, cf, de, ef, bf, cd. Graph B (vertices a–f): edges af…
- Which of the following statements are true about sets? A. 0 ∈ ∅ B. ∅ ∈ {0} C. ∅ ∈ {∅} D. {∅} ∈ {∅} E. {∅} ⊂ {∅, {∅}} Choose the correct ans…
- Consider the following relations on {1, 2, 3, 4}. Which of the following relations are reflexive? (A) R₁ = {(1,1),(1,2),(2,1),(2,2),(3,4),(…
- Let p be "It is a hot day" and q be "The temperature is 48°C". Write in simple sentences the meaning of ¬p ∧ ¬q.
- A graph G with n ≥ 3 vertices is a Hamiltonian graph if the degree of each vertex is greater than or equal to