If a simple graph G contains n vertices and m edges, the number of edges in…
If a simple graph G contains n vertices and m edges, the number of edges in the complement graph G' (the complement of G) is ___________
Answer: A. (n2 − n − 2m) / 2 — ConceptIn a simple graph on n vertices, the complement G' contains exactly those vertex pairs that are NOT edges of G. The total number of distinct vertex…
- A.
(n2 − n − 2m) / 2
- B.
(n2 + n + 2m) / 2
- C.
(n2 + n − 2m) / 2
- D.
(n2 − n + 2m) / 2
Attempted by 103 students.
Show answer & explanation
Correct answer: A
Concept
In a simple graph on n vertices, the complement G' contains exactly those vertex pairs that are NOT edges of G. The total number of distinct vertex pairs equals the number of edges of the complete graph Kn, namely nC2 = n(n−1)/2. Therefore edges(G') = (all vertex pairs) − (edges of G).
Application
Count all vertex pairs: a complete graph on n vertices has n(n−1)/2 edges.
Edges already used by G: m.
Edges of the complement: n(n−1)/2 − m.
Put over a common denominator: (n2 − n)/2 − m = (n2 − n − 2m)/2.
Cross-check
Test the extremes. If G is already complete, m = n(n−1)/2, and the formula gives (n2 − n − 2·(n(n−1)/2))/2 = 0 — correct, since the complement of a complete graph has no edges. If G is empty, m = 0, and the formula gives n(n−1)/2, the full complete graph, also as expected.