The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.6k 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
asked in Graph Theory by Veteran (69k points)
retagged by | 1.6k 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 Boss (8.5k 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 (733 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.
exactly!


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

33,593 questions
40,128 answers
114,021 comments
38,389 users