Consider an undirected graph G with 100 nodes. The maximum number of edges to…
2013
Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is
- A.
2451
- B.
4950
- C.
4851
- D.
9900
Attempted by 50 students.
Show answer & explanation
Correct answer: C
To maximize edges in a disconnected graph with n nodes, isolate one node and form a complete graph with the remaining n-1 nodes. For n equals 100, this means a complete graph of 99 nodes. The number of edges is calculated as 99 times 98 divided by 2, which equals 4851.
A video solution is available for this question — log in and enroll to watch it.