The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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.1k
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
(
59.9k
points)
retagged
Dec 3, 2015
by
Akash Kanase

1.1k
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
(
34.1k
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
(
59.9k
points)

639
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
(
41.2k
points)

4.7k
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? (A) K4 is a planar while Q3 is not (B) Both K4 and Q3 are planar (C) Q3 is planar while K4 is not (D) Neither K4 nor Q3 is planar
asked
Sep 29, 2014
in
Graph Theory
by
jothee
Veteran
(
115k
points)

1.3k
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
(
115k
points)

2.1k
views
gate20143
graphtheory
graphplanarity
normal
outofsyllabusnow
+10
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
(
18.3k
points)

1.4k
views
gate2005
graphtheory
graphplanarity
normal
outofsyllabusnow
+16
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
(
18.3k
points)

2.3k
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
(
59.9k
points)

339
views
gate1992
compilerdesign
macros
easy
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
Need suggestions for what to do next after Gate ??
For GATECSE Admissions 2019
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
All categories
General Aptitude
1.5k
Engineering Mathematics
7.1k
Discrete Mathematics
4.9k
Mathematical Logic
1.9k
Set Theory & Algebra
1.3k
Combinatory
873
Graph Theory
802
Probability
1k
Linear Algebra
692
Calculus
493
Digital Logic
2.7k
Programming & DS
4.9k
Algorithms
4.2k
Theory of Computation
5.3k
Compiler Design
2.1k
Operating System
4k
Databases
4k
CO & Architecture
3.5k
Computer Networks
4k
Non GATE
1.4k
Others
1.5k
Admissions
559
Exam Queries
555
Tier 1 Placement Questions
23
Job Queries
69
Projects
18
Follow @csegate
Recent Blog Comments
I am not a ranker so you might not believe on my...
What is the status on appsgate website? I...
Can the ppt be made available?
47,928
questions
52,334
answers
182,380
comments
67,807
users