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
Recent questions tagged graphplanarity
+2
votes
1
answer
1
UGCNETJune2019II4
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? $6$ $8$ $12$ $20$
asked
Jul 2
in
Graph Theory
by
Arjun
Veteran
(
418k
points)

127
views
ugcnetjune2019ii
graphplanarity
handshakingtheorem
0
votes
0
answers
2
What to study & from where to study  Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.
asked
Dec 29, 2018
in
Graph Theory
by
Krishna Sai Vootla
(
21
points)

201
views
syllabus
engineeringmathematics
graphtheory
graphplanarity
graphisomorphism
vertexcover
0
votes
0
answers
3
Planar graph
In a connected 3 regular graph, every planar region is bounded by exactly 5 edges, then count no of edges?
asked
Dec 21, 2018
in
Graph Theory
by
Shamim Ahmed
Active
(
2.3k
points)

80
views
graphtheory
graphplanarity
0
votes
1
answer
4
Planar Graph
Let G be a simple connected planar graph with 14 vertices and 20 edges. Number of closed regions in planar embedding of the graph is ?
asked
Dec 2, 2018
in
Graph Theory
by
Na462
Loyal
(
6.7k
points)

204
views
graphtheory
graphplanarity
0
votes
1
answer
5
Planar Graph
Can minimum degree of a planar graph be $5$? Give some example
asked
Oct 23, 2018
in
Graph Theory
by
srestha
Veteran
(
115k
points)

242
views
graphtheory
graphplanarity
+2
votes
1
answer
6
planar region
How many planar regions? How many closed regions? and how many are unbounded? How many of then are bounded by a cycle of length $4$ ? Now, for example (a different question, not related to above diagram ) a question says, In a connected 3 regular graph, ... region is bounded by exactly 5 edges, then count no of edges? Please explain the last QS with the help of Euler's equation.
asked
Dec 26, 2016
in
Graph Theory
by
dd
Veteran
(
56.7k
points)

1.1k
views
graphtheory
graphplanarity
+2
votes
1
answer
7
Planar graph  Kenneth
A planar graph has, $\large\color{maroon}{\text{k}}$ connected components $\large\color{maroon}{\text{v}}$ vertices $\large\color{maroon}{\text{e}}$ edges If the plane is divided into $\large\color{maroon}{\text{r}}$ ... $\large\color{maroon}{\text{v}}$ , $\large\color{maroon}{\text{e}}$ and $\large\color{maroon}{\text{r}}$ ?
asked
Dec 20, 2016
in
Graph Theory
by
dd
Veteran
(
56.7k
points)

257
views
graphtheory
graphplanarity
+16
votes
2
answers
8
GATE19903vi
Which of the following graphs is/are planner?
asked
Nov 27, 2016
in
Graph Theory
by
makhdoom ghaya
Boss
(
29.7k
points)

999
views
gate1989
normal
graphtheory
graphplanarity
descriptive
+14
votes
2
answers
9
GATE19903xi
Choose the correct alternatives (More than one may be correct). A graph is planar if and only if, It does not contain subgraphs homeomorphic to $k_{5}$ and $k_{3, 3}$. It does not contain subgraphs isomorphic to $k_{5}$ or $k_{3, 3}$. It does not contain a subgraph isomorphic to $k_{5}$ or $k_{3, 3}$ It does not contain a subgraph homeomorphic to $k_{5}$ or $k_{3, 3}$.
asked
Nov 23, 2016
in
Graph Theory
by
makhdoom ghaya
Boss
(
29.7k
points)

1.6k
views
gate1990
normal
graphtheory
graphplanarity
+1
vote
1
answer
10
GATE19872e
State whether the following statement is TRUE or FALSE: There is a lineartime algorithm for testing the planarity of finite graphs.
asked
Nov 9, 2016
in
Graph Theory
by
makhdoom ghaya
Boss
(
29.7k
points)

256
views
gate1987
graphtheory
graphplanarity
nongate
+4
votes
2
answers
11
UGCNETDec2012III46
Two graphs A and B are shown below: Which one of the following statements is true? Both A and B are planar Neither A nor B is planar A is planar and B is not B is planar and A is not
asked
Jul 13, 2016
in
Graph Theory
by
jothee
Veteran
(
100k
points)

776
views
ugcnetdec2012iii
graphtheory
graphplanarity
+3
votes
3
answers
12
UGCNETJune2012III72
G1 and G2 are two graphs as shown: Both G1 and G2 are planar graphs Both G1 and G2 are not planar graphs G1 is planar and G2 is not planar G1 is not planar and G2 is planar
asked
Jul 8, 2016
in
Graph Theory
by
jothee
Veteran
(
100k
points)

1.2k
views
ugcnetjune2012iii
graphtheory
graphplanarity
+1
vote
1
answer
13
condition for planar graph??
what is the sufficient condition so that we say given graph is planar or not???
asked
Nov 21, 2015
in
Graph Theory
by
Hira Thakur
Boss
(
13.2k
points)

443
views
graphplanarity
+17
votes
3
answers
14
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.7k
points)

5k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+1
vote
2
answers
15
planar graphs
Is there any subgraph homoemorphic to K5 present in G1 for the following question? Which one of the following graphs is NOT planar? (A) G1 (B) G2 (C) G3 (D) G4 In this question planar drawings( no 2 edges intersect) for G2, G3 and G4 exists, thats why ... 't find any subgraph homoemorphic to K5 in G1 as a graph is non planar iff it contains a subgraph homoemorphic to K5 or K3,3...
asked
Dec 14, 2014
in
Graph Theory
by
dhingrak
Active
(
1k
points)

424
views
graphtheory
graphplanarity
+3
votes
2
answers
16
No of vertices in Planar graph
If G is a planar graph with 35 regions each of degree 6 the no of vertices are a) 70 b) 80 c) 72 d) 62 What does degree of a region specify here?
asked
Nov 30, 2014
in
Graph Theory
by
dhingrak
Active
(
1k
points)

590
views
graphplanarity
outofsyllabusnow
+14
votes
1
answer
17
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
(
100k
points)

1.5k
views
gate2011
graphtheory
graphplanarity
normal
outofsyllabusnow
+14
votes
2
answers
18
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
(
100k
points)

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

1.6k
views
gate2005
graphtheory
graphplanarity
normal
outofsyllabusnow
+7
votes
2
answers
20
GATE200510
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is: $6$ $8$ $9$ $13$
asked
Sep 21, 2014
in
Graph Theory
by
gatecse
Boss
(
16.1k
points)

1.1k
views
gate2005
graphtheory
graphplanarity
+6
votes
3
answers
21
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
(
52.1k
points)

692
views
gate1992
graphtheory
normal
graphplanarity
outofsyllabusnow
+7
votes
1
answer
22
GATE199201,x
(x) Maximum number of edges in a planar graph with n vertices is _____
asked
Sep 13, 2014
in
Graph Theory
by
Kathleen
Veteran
(
52.1k
points)

1.3k
views
gate1992
graphtheory
graphplanarity
easy
outofsyllabusnow
+16
votes
3
answers
23
GATE200823
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertexcover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$
asked
Sep 12, 2014
in
Graph Theory
by
Kathleen
Veteran
(
52.1k
points)

2.8k
views
gate2008
graphtheory
normal
graphplanarity
+17
votes
2
answers
24
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
(
16.1k
points)

2.5k
views
gate2012
graphtheory
graphplanarity
normal
outofsyllabusnow
To see more, click for the
full list of questions
or
popular tags
.
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
Previous Years Question Papers : ISI  MMA, PCB, DCG
Previous Years Question Papers : CMI  Computer Science
Minimum Number of States in a DFA accepting a binary number divisible by 'n'
GATE 2020 Application Form Opened!
My GATE Preparation Journey
Follow @csegate
Recent questions tagged graphplanarity
Recent Blog Comments
Feedback for next edition (if ever there's...
Is go book still available,I want to buy it
will pdfs be uploaded ?
50,092
questions
55,269
answers
190,799
comments
86,083
users