# 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 1 Explanation:
 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 2 Explanation:
 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 3 Explanation:
 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 4 Explanation:
 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
Question 5 Explanation:
 Question 6
Let G be the non-planar graph with the minimum possible number of edges. Then G has
 A 9 edges and 5 vertices B 9 edges and 6 vertices C 10 edges and 5 vertices D 10 edges and 6 vertices
GATE CSE 2007   Discrete Mathematics
Question 6 Explanation:
 Question 7
Which one of the following graphs is NOT planar? A G1 B G2 C G3 D G4
GATE CSE 2005   Discrete Mathematics
Question 7 Explanation:
 Question 8
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:
 A 6 B 8 C 9 D 13
GATE CSE 2005   Discrete Mathematics
Question 8 Explanation:
 Question 9
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only:
A non-planar 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
GATE CSE 1992   Discrete Mathematics
Question 9 Explanation:
There are 9 questions to complete.