The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Lists
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
GATE20074
+11
votes
2k
views
Let $G$ be the nonplanar graph with the minimum possible number of edges. Then $G$ has
9 edges and 5 vertices
9 edges and 6 vertices
10 edges and 5 vertices
10 edges and 6 vertices
gate2007
graphtheory
normal
outofsyllabusnow
asked
Sep 22, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.6k
points)
retagged
Dec 3, 2015
by
Akash Kanase

2k
views
Facebook
Google+
Twitter
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
2
Answers
+15
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
Jan 2, 2015
by
jayendra
Loyal
(
8.2k
points)
selected
Dec 3, 2015
by
Akash Kanase
comment
0
is there any other way to find non planar graph ?
0
answer is b or c?
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....
Please
log in
or
register
to add a comment.
–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
Mar 17, 2017
by
Beyonder
Junior
(
623
points)
comment
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 nonplanar as it is in option b although option c is nonplanar 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 nonplanar 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 nonplaner graph if they satisfies this equation or not.
0
exactly!
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Answer:
B
Related questions
+31
votes
5
answers
1
GATE200723
Which of the following graphs has an Eulerian circuit? Any $k$regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
asked
Sep 22, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.6k
points)

3.6k
views
gate2007
graphtheory
normal
graphconnectivity
eulergraph
+1
vote
0
answers
2
GATE200728
Consider the series $x_{n+1} = \frac{x_n}{2}+\frac{9}{8x_n},x_0 = 0.5$ obtained from the NewtonRaphson method. The series converges to 1.5 $\sqrt{2}$ 1.6 1.4
asked
Sep 22, 2014
in
IS&Software Engineering
by
Kathleen
Veteran
(
59.6k
points)

234
views
gate2007
numericalmethods
newtonraphson
normal
outofsyllabusnow
+5
votes
2
answers
3
GATE200766, ISRO201671
In a token ring network the transmission speed is 10$^7$ bps and the propagation speed is 200 meters/$\mu$s. The 1bit delay in this network is equivalent to: 500 meters of cable. 200 meters of cable. 20 meters of cable. 50 meters of cable.
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
59.6k
points)

4.3k
views
gate2007
computernetworks
tokenring
outofsyllabusnow
isro2016
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
Recent Posts
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
All categories
General Aptitude
1.4k
Engineering Mathematics
5.9k
Discrete Mathematics
4.1k
Mathematical Logic
1.7k
Set Theory & Algebra
1k
Combinatory
733
Graph Theory
667
Probability
840
Linear Algebra
564
Calculus
413
Digital Logic
2.3k
Programming & DS
4.3k
Algorithms
3.7k
Theory of Computation
4.6k
Compiler Design
1.7k
Operating System
3.4k
Databases
3.4k
CO & Architecture
2.9k
Computer Networks
3.4k
Non GATE
1.2k
Others
1.3k
Admissions
506
Exam Queries
482
Tier 1 Placement Questions
22
Job Queries
64
Projects
15
Follow @csegate
Gatecse
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,903
questions
47,558
answers
146,288
comments
62,305
users