The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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 (52.1k points)
retagged by | 2.7k views

3 Answers

+17 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.1k 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....

@shankargadri 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
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)
answered by Junior (959 points)
–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 (489 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.

Related questions

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
49,814 questions
54,518 answers
75,287 users