Question

Let G be the non-planar graph with the minimum possible number of edges. Then G has

• A. 9 edges and 5 vertices
• B. 9 edges and 6 vertices
• C. 10 edges and 5 vertices
• D. 10 edges and 6 vertices

Answer 1

The correct option is B 9 edges and 6 vertices

$K_5\text{and}{K}_{3,3}$ are the smallest non planar graph $K_5$ has 5 vertices and ${}^5{C}_2=10$ edges and $K_5$ has 6 vertices and 3 × 3 = 9 edges. So, the n planar graph with minimum number of edges $K_{3,3}$ with 9 edges and 6 vertices.

Note: $K_5$ is the non planar graph with minimum number of vertices.