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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
GATE199201,x
+7
votes
1.2k
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
Veteran
(
52k
points)
retagged
Dec 3, 2015
by
Akash Kanase

1.2k
views
answer
comment
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
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 25, 2015
by
Rajarshi Sarkar
Boss
(
33.8k
points)
selected
Apr 25, 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?
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
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
Veteran
(
52k
points)

673
views
gate1992
graphtheory
normal
graphplanarity
outofsyllabusnow
+16
votes
3
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
Boss
(
29.3k
points)

4.9k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+14
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
Veteran
(
96.1k
points)

1.5k
views
gate2011
graphtheory
graphplanarity
normal
outofsyllabusnow
+14
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
Veteran
(
96.1k
points)

2.2k
views
gate20143
graphtheory
graphplanarity
normal
outofsyllabusnow
+11
votes
2
answers
5
GATE200547
Which one of the following graphs is NOT planar? G1 G2 G3 G4
asked
Sep 21, 2014
in
Graph Theory
by
gatecse
Boss
(
16k
points)

1.5k
views
gate2005
graphtheory
graphplanarity
normal
outofsyllabusnow
+17
votes
2
answers
6
GATE201217
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to (A) 3 (B) 4 (C) 5 (D) 6
asked
Aug 5, 2014
in
Graph Theory
by
gatecse
Boss
(
16k
points)

2.4k
views
gate2012
graphtheory
graphplanarity
normal
outofsyllabusnow
+2
votes
1
answer
7
GATE199201,vii
Macro expansion is done in pass one instead of pass two in a two pass macro assembler because _________
asked
Sep 13, 2014
in
Compiler Design
by
Kathleen
Veteran
(
52k
points)

348
views
gate1992
compilerdesign
macros
easy
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
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
IIIT Hyerabad Interview Expeience  MS by Research in CSE
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
873
Graph Theory
803
Probability
992
Linear Algebra
688
Calculus
488
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.4k
Admissions
596
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent Blog Comments
Yes. Address is not a candidate key 😊
Can two people order gohard copy at same address?
Congratulations and Welcome to IIITH !
Payment ID itself confirms the order.
Sir , my payment id is 250986176 could you...
49,534
questions
54,122
answers
187,321
comments
71,040
users