The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 votes

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
asked in Graph Theory by Veteran (59.4k points)
retagged by | 1.8k views

2 Answers

+14 votes
Best answer
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.
answered by Loyal (8.3k points)
selected by
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....
–2 votes
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
answered by Junior (607 points)
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,487 questions
42,747 answers
42,138 users