Question

Which of the following statements are correct?
• [A.] An adjacency matrix uses \(O(n^2)\) of the adjacency list is \(O(n + m)\)
• [B.] The adjacency matrix requires \(O(n^2)\) memory
• [C.] In an undirected graph, the sum of lengths of adjacency lists is \(2m\)
• [D.] The memory requirement of adjacency list is dependent on the number of edges in the graph
Choose the correct answer from the options given below:

• A. A, B, C only
• B. B, C only
• C. A, B, D only
• D. A, B, C, D

Hint:

Adjacency matrix → dense graphs, Adjacency list → sparse graphs.

Answer 1

The Correct Option is D

Concept: Graph representations include adjacency matrix and adjacency list.

Step 1: Adjacency Matrix Complexity
• Requires \(n \times n\) space
• Hence \(O(n^2)\) ✔ Statement B is correct.

Step 2: Adjacency List Complexity
• Stores vertices and edges
• Space: \(O(n + m)\) ✔ Statement A is correct.

Step 3: Undirected Graph Property
• Each edge contributes twice
• Total adjacency list length = \(2m\) ✔ Statement C is correct.

Step 4: Memory Dependence
• Adjacency list grows with number of edges ✔ Statement D is correct.

Step 5: Final conclusion All statements are correct. \[ \boxed{(4)} \]