2.7k views

Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has

1. 9 edges and 5 vertices
2. 9 edges and 6 vertices
3. 10 edges and 5 vertices
4. 10 edges and 6 vertices
retagged | 2.7k views

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.
selected
0
is there any other way to find non planar graph ?
0
0
@ Regina Phalange : the question is asking minimum edges thus it is B  6 vertices with 9 edges.
0
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
0
you can draw a graph with 6 vertices and 11 edges and still it is planner....
+1

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

+1 vote
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)
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
0
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.
0
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.
0
exactly!

+1 vote
1
2