Edges of a complete graph — Aptitude Question
Edges of a complete graph: How many edges does a complete undirected graph on 12 vertices have? Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Easy
- Time target: 45 seconds
Question
How many edges does a complete undirected graph on 12 vertices have?
Options
- 12
- 66
- 132
- 144
Show the answer and the worked solution
Correct answer: B. 66
Worked solution
- A complete graph joins every pair of distinct vertices with exactly one edge.
- The number of unordered pairs is C(12, 2) = (12 × 11) / 2 = 66.
- So the graph has 66 edges. A directed complete graph would have twice as many.
Answer: 66.
The idea
Undirected edges are unordered pairs, so the count is n(n − 1)/2. Forgetting to divide by two is the standard slip and is exactly what one of the distractors rewards.
Shortcut. Each of the 12 vertices has degree 11, and each edge is counted from both ends: 12 × 11 ÷ 2 = 66.
Common trap. 132 is 12 × 11 without halving, which counts each undirected edge twice, as if the graph were directed.
All Data Structures & Algorithms questions · placement mock tests