A simple graph G with n vertices is connected if the graph has:
2013
A simple graph G with n vertices is connected if the graph has:
- A.
(n − 1)(n − 2)/2 edges
- B.
More than (n − 1)(n − 2)/2 edges
- C.
Less than (n − 1)(n − 2)/2 edges
- D.
∑ from i = 1 to k of C(nᵢ, 2) edges
Attempted by 61 students.
Show answer & explanation
Correct answer: B
A simple graph with n vertices is guaranteed connected if the number of edges exceeds (n−1)(n−2)/2. This threshold represents the maximum edges possible in a disconnected graph where one vertex is isolated and the rest form a complete subgraph. Therefore, any edge count above this value ensures connectivity.
A video solution is available for this question — log in and enroll to watch it.