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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
GATE199201,x
+7
votes
1.8k
views
(x) Maximum number of edges in a planar graph with n vertices is _____
gate1992
graphtheory
graphplanarity
easy
outofsyllabusnow
asked
Sep 13, 2014
in
Graph Theory
by
Kathleen
retagged
Dec 3, 2015
by
Akash Kanase

1.8k
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+9
votes
Best answer
Answer: 3n  6
Ref:
http://mathoverflow.net/questions/124116/maximumnumberofedgesinaplanargraph
answered
Apr 26, 2015
by
Rajarshi Sarkar
selected
Apr 26, 2015
by
Arjun
comment
0
i think it is 2n2
if n=2 then edges will be 1 it is also a planar graph but according to your equation it becomes 0
0
@ suneetha 2n4 (not 2n2) its true when the graph has no cycle of lenght 3.
0
they didn't represent about whether it should have cycle or not?
0
if n is even then the equation comes like 2(n1)
if n is odd then the equation comes like 2n1
then what is the answer for this question?
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
+6
votes
3
answers
1
GATE199202,viii
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only: (viii) A nonplanar graph with minimum number of vertices has (a) 9 edges, 6 vertices (b) 6 edges, 4 vertices (c) 10 edges, 5 vertices (d) 9 edges, 5 vertices
asked
Sep 13, 2014
in
Graph Theory
by
Kathleen

888
views
gate1992
graphtheory
normal
graphplanarity
outofsyllabusnow
+20
votes
4
answers
2
GATE2015154
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
asked
Feb 14, 2015
in
Graph Theory
by
makhdoom ghaya

6.6k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+15
votes
1
answer
3
GATE201117
K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar
asked
Sep 29, 2014
in
Graph Theory
by
jothee

2.2k
views
gate2011
graphtheory
graphplanarity
normal
outofsyllabusnow
+15
votes
2
answers
4
GATE2014352
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar embedding, the ... less than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
asked
Sep 28, 2014
in
Graph Theory
by
jothee

3k
views
gate20143
graphtheory
graphplanarity
normal
outofsyllabusnow
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
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.2k
Discrete Mathematics
5.9k
Mathematical Logic
2.1k
Set Theory & Algebra
1.5k
Combinatory
1.4k
Graph Theory
846
Probability
1k
Linear Algebra
732
Calculus
600
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
Can someone tell me how to check part B marks?...
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,497
answers
201,864
comments
95,320
users