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:

There are 5 questions to complete.