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

Comments

@Siddiqui_Danish

I think it is in syllabus bro

---

https://gateoverflow.in/8364/gate-cse-2015-set-1-question-54?show=8364#q8364
under the coment section someone asked arjun sir to remove the out of syllabustag  they have removed the tag for several questions still some inconsistencies are there

 

---

@Siddiqui_Danish

Excellent find bro. That would make sense. 

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

@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

Don't Check Planarity Using this formula e <= 3n -6

Because If Graph G is Planar then e <= 3n-6 but the Vice-Versa is not TRUE

In Option B : 9 edges and 6 vertices , It is K3,3 which is a non planar graph

😎Like if you got it.

Answer 4

For a graph to be non-planar, it must be complex enough to contain a specific structure. As established by Kuratowski's Theorem, it must contain a version of either a K5​ or a K3,3​ subgraph.

• To form a K3,3​ structure, you need at least 6 vertices and 9 edges.

• To form a K5​ structure, you need at least 5 vertices and 10 edges.

A graph with only 5 edges falls far short of the minimum of 9 edges required for the simplest non-planar structure (K3,3​). You cannot build a K3,3​ or a K5​ with only 5 edges, so the graph must be planar.

Answer 5

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!