The GATE Grind

GATE 2008 CS – Question 23

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Which is true for every planar graph on n vertices?

  1. Graph is connected.
  2. Graph is Eulerian.
  3. Graph has a vertex cover of size at most3n/4.
  4. Graph has an independent set of size at least n/3.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Graph has a vertex cover of size at most3n/4.

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →