The maximum number of edges in a n-node undirected graph without self loops is
200820022011
The maximum number of edges in a n-node undirected graph without self loops is
- A.
n2
- B.
n * (n-1)/2
- C.
n - 1
- D.
(n + 1) * n/2
Attempted by 216 students.
Show answer & explanation
Correct answer: B
The maximum number of edges in an undirected graph with n nodes and no self-loops is achieved when the graph is complete.
In a complete graph, every pair of distinct vertices is connected by an edge. Since there are n vertices, each can connect to (n-1) others. To avoid double-counting undirected edges, we divide by 2. Thus, the formula is n(n-1)/2.
A video solution is available for this question — log in and enroll to watch it.