Question

Which of the following statements are TRUE, where $|E|$ represents the number of edges?
(A). In case of a directed graph, the sum of lengths of all the adjacency list is |E|
(B). For an undirected graph, the sum of the lengths of all the adjacency list is 2|E|
(C). For a dense graph, adjacency matrix representation is preferable
(D). The memory requirement of the adjacency matrix of a graph is dependent on the number of edges

• A. (A), (B) and (D) only
• B. (A), (B) and (C) only
• C. (A), (B), (C) and (D)
• D. (A), (B) and (C) only

Hint:

In dense graphs, adjacency matrices are more efficient than adjacency lists. The memory for an adjacency matrix depends on the number of vertices, not edges.

Answer 1

The Correct Option is C

Step 1: Understand the statements.
- **(A)** In a directed graph, the sum of lengths of all the adjacency lists is **$|E|$**. This is true because each edge is listed exactly once in the adjacency list of a directed graph.
- **(B)** In an undirected graph, the sum of the lengths of all the adjacency lists is **$2|E|$**. Each edge is counted twice in an undirected graph, once for each endpoint.
- **(C)** For a dense graph, adjacency matrix representation is preferable. This is true because dense graphs have a large number of edges, making an adjacency matrix (which stores the presence of edges between every pair of vertices) more efficient than an adjacency list.
- **(D)** The memory requirement of the adjacency matrix of a graph is dependent on the number of edges. This is false; the memory requirement of an adjacency matrix depends on the number of vertices, not edges.

Step 2: Conclusion.
Thus, the correct answer is **(3) (A), (B), (C) and (D)**.