GATE CSE 2007 | Question: 4

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

ans is B:

non planar graph with smallest number of edges is K3,3; it has 9 edges and 6 vertices

K5 is also non planar but it has 10 edges and 5 vertices.

Comments

is there any other way to find non planar graph ?

---

answer is b or c?

---

@ Regina Phalange : the question is asking minimum edges thus it is B  6 vertices with 9 edges.

---

There is nothing specific said about k3,3 in question? Bipartite sets have a very specific condition, we cant make any assumptions here

We have to use eulars formula here, 'c' is the answer

---

you can draw a graph with 6 vertices and 11 edges and still it is planner....

---

@shankargadri The question you're talking about came in 1992 paper. This GATE 2007 question has asked minimum number of "edges".

---

Can any one explain why option a is not correct answer?

---

@ Sona Barman @reena_kandari  @Regina Phalange

Why is option B correct  and not option C ?

I mean for option B we do have the planar graph mentioned in the image below

Answer 2

In planar graph, any face (except possibly the outer line) is bounded by atleast three edges and every edge touches atmost two faces.
Using Euler’s formula it states that,
if v ≥ 3 then e ≤ 3v-6
where e=edges
v=vertices
Go through the options
i) 9e and 5v ⇒ 9≤3(5)-6
⇒ 9≤15-6
⇒ 9≤9 (It’s satisfies planar graph)
ii) 9e and 6v ⇒ 9≤3(6)-6
⇒ 9≤12 (It’s planar graph)
iii) 10e and 5v ⇒ 10≤3(5)-6
⇒ 10≤9 (It’s not satisfies planar graph condition)
So, option C is non-planar graph.
iv) 10e and 6v ⇒ 10≤3(6)-6
⇒ 10≤12 (It’s planar graph)

Comments

Correct answer is option (B) not c

Answer 3

We can check it with Euler's formula V - e + r = 2 and 3r $\leq$ 2e.
Take each option and check whether 3r $\leq$ 2e after finding value of r using
v - e + r = 2.
if its satisfies the condition than its is planar otherwise not.
For all option its satisfies except option c

Comments

No you are wrong if it not satisfies then it is non- planar but if it satisfies we cant say anything about it it can be planar or non-planar as it is in option b although option c is non-planar but it dont have minimum possible number of edges as mentioned in the question. Moreover option b represents K3,3 which is kurotowski's minimum edge non-planar graph so option b is correct.

---

yes, @neelesh you are correct

every planer graph satisfies euler's formula, if it doesnt satisifes then it is non planer for sure.

but we can not say about non-planer graph if they satisfies this equation or not.

---

exactly!