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

K4 is planar while Q3 is not | |
Both K4 and Q3 are planar | |
Q3 is planar while K4 is not | |
Neither K4 not Q3 is planar |
Question 4 Explanation:
Question 5 |
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 vertex-cover of size at most 3n/4 | |
The graph has an independent set of size at least n/3 |
Question 5 Explanation:
Question 6 |
Let G be the non-planar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices | |
9 edges and 6 vertices | |
10 edges and 5 vertices | |
10 edges and 6 vertices |
Question 6 Explanation:
Question 7 |
Which one of the following graphs is NOT planar?


G1 | |
G2 | |
G3 | |
G4 |
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:
6 | |
8 | |
9 | |
13 |
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 non-planar graph with minimum number of vertices has
9 edges, 6 vertices | |
6 edges, 4 vertices | |
10 edges, 5 vertices | |
9 edges, 5 vertices |
Question 9 Explanation:
There are 9 questions to complete.