Planar Graph


Question 1
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.
A
15
B
13
C
11
D
10
GATE CSE 2021 SET-1   Discrete Mathematics
Question 2
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?
A
In any planar embedding, the number of faces is at least \frac{n}{2}+2
B
In any planar embedding, the number of faces is less than \frac{n}{2}+2
C
There is a planar embedding in which the number of faces is less than \frac{n}{2}+2
D
There is a planar embedding in which the number of faces is at most \frac{n}{\delta +1}
GATE CSE 2014 SET-3   Discrete Mathematics


Question 3
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
GATE CSE 2012   Discrete Mathematics
Question 4
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 planar while Q3 is not
B
Both K4 and Q3 are planar
C
Q3 is planar while K4 is not
D
Neither K4 not Q3 is planar
GATE CSE 2011   Discrete Mathematics
Question 5
Which of the following statements is true for every planar graph on n vertices?
A
The graph is connected
B
The graph is Eulerian
C
The graph has a vertex-cover of size at most 3n/4
D
The graph has an independent set of size at least n/3
GATE CSE 2008   Discrete Mathematics


There are 5 questions to complete.

Leave a Comment