# GATE1992-02,viii

6 votes
1k views

Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only:

(viii) A non-planar graph with minimum number of vertices has

(a) 9 edges, 6 vertices

(b) 6 edges, 4 vertices

(c) 10 edges, 5 vertices

(d) 9 edges, 5 vertices

edited

## 3 Answers

11 votes

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

5 votes
Answer: C
0
Please Explain!
2
k5, k3,3 which are non planner , but k5 with minimum vertex ... 5, so no of edges n(n-1)/2 = 10 edges .
0 votes

Answer: C

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$

0

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..

## Related questions

7 votes
1 answer
1
2.2k views
(x) Maximum number of edges in a planar graph with n vertices is _____
0 votes
1 answer
2
733 views
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Bit-slice processors can be cascaded to get any desired word length processor speed of operation is independent of the word length configured do not contain anything equivalent of program counter in a 'normal' microprocessor Contain only the data path of a 'normal' CPU
22 votes
4 answers
3
7.3k views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
15 votes
1 answer
4
2.5k views
K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar