Multiple choice

Which of the following statements is true for every planar graph on n vertices?

  1. The graph is connected

  2. The graph is Eulerian

  3. The graph has a vertex-cover of size at most 3n/4

  4. The graph has an independent set of size at least n/3

Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

A planar Graph can be drawn on the plane in such a way that its edges may intersect only at their end points. Hence each plannar graph is connected on n vertices.