Let G be the non-planar graph with the minimum possible number of edges. Then…
2007
Let G be the non-planar graph with the minimum possible number of edges. Then G has
- A.
10 edges and 6 vertices
- B.
10 edges and 5 vertices
- C.
9 edges and 6 vertices
- D.
9 edges and 5 vertices
Attempted by 273 students.
Show answer & explanation
Correct answer: C
Answer: 9 edges and 6 vertices.
Reason:
Kuratowski's theorem: a finite graph is non-planar if and only if it contains a subdivision of K5 or K3,3.
Any subdivision of K5 has at least 10 edges; any subdivision of K3,3 has at least 9 edges.
Therefore any non-planar graph must have at least 9 edges, and this lower bound is attained by K3,3, which has 6 vertices and 9 edges.
As a supporting check, for 5 vertices the planar upper bound is 3n-6 = 9 edges, so a non-planar graph on 5 vertices would need more than 9 edges (hence at least 10). This rules out any 5-vertex graph with 9 edges as the minimal non-planar example.
Conclusion: The non-planar graph with the minimum possible number of edges has 9 edges and 6 vertices (example: K3,3).
A video solution is available for this question — log in and enroll to watch it.