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?

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.