1,501 views

A non-planar graph with minimum number of vertices has

1. $9$ edges, $6$ vertices
2. $6$ edges, $4$ vertices
3. $10$ edges, $5$ vertices
4. $9$ edges, $5$ vertices

### Subscribe to GO Classes for GATE CSE 2022

A non-planar graph with minimum number of vertices has 10 edges, 5 vertices i.e K5

A non-planar graph with minimum number of edges has 9 edges, 6 vertices i.e K3,3

k5, k3,3 which are non planner , but k5 with minimum vertex ... 5, so no of edges n(n-1)/2 = 10 edges .

Using  Planarity criteria relation  $e \leq 3\times v -6,$

All other option satisfies this relation except option $(C)$

i.e$10 \nleqslant 3 \times 5-6$

by

### 1 comment

sir , I think it is not sufficient condition..because  for K3,3 , 9<= 3*6 - 6 but it is non-planar graph..please correct me if I m wrong..

1
3,495 views
2
3