GATE CSE 1992 | Question: 02,viii

Question

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

Comments

just satisfy both this cond. i) e>3n-6(when no of vertices is at least 3 and exists triangle.)

 ii)e>2n-4(when no of vertices is at least 3 and exists no triangle.)

Answer 1

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

Comments

answer is C.

---

got it

---

 
6 vertices, 9 edges this is still planar 

---

@Kishan Songara What if you make complete bipartite K3,3? It will be non planar. It has 6 Vertices, 9 Edges

Answer 2

Answer: C

Comments

Please Explain!

---

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

Answer 3

.

Answer 4

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$

Comments

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

---

@ankitgupta.1729

This condition is used like this :-

Let G be a connected graph with ∣V∣ ≥ 3 (where ∣V∣ is the number of vertices).

If |E| > 3*|v| - 6  then  G is Not a planar graph.

If |E| <= 3*|v| - 6  then G may or may not be planar.

---

But to use this condition, we need the guarantee for it to be connected, right? the question is concerned only about the minimum number of vertices and no mention about edges. so can't rely on this criterion completely.

Answer 5

 

C