2k 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 | 2k 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....
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!