Graph Theory - II CIA Quiz

When will we say that a graph is a planar graph?

• A graph is planar if it can be drawn on a plane without edge crossings.
• A graph is planar if it can be drawn in three dimensions.
• A graph is planar if it contains no cycles.
• A graph is planar if it has at least three vertices.

A closed Jordan curve partitions the plane into ............ regions.

• three
• four
• two
• one

How many bounded region does the plane graph has when we partitions the plane?

• 2F, where F is the number of faces in the graph.
• F - 1, where F is the number of faces in the graph.
• F + 1, where F is the number of faces in the graph.
• F - 2, where F is the number of faces in the graph.

Which one of the following is a Euler formula for planar (p, q) graph with r number of faces?

• p + q + r = 3
• p - r = 1
• p - q + r = 2
• p + q - r = 0

Which of the following is/are planar graphs?

There are exactly .............. regular polyhedra

• 4
• 6
• 8
• 5

• (ii) A graph is planar iff it contains a contraction of K_5
• (ii), (iii), (iv)
• (i) Every subgraph of a nonplanar graph is planar
• (iv) Every subdivision of a planar graph is nonplanar

True or False: Every graph with p vertices is p-colourable.

• True

• False

• True

• False

What is the Chromatic number of complete graph and complement of complete graph?

• K_n has chromatic number n; complement of K_n has chromatic number 1.
• K_n has chromatic number n; complement of K_n has chromatic number n.
• K_n has chromatic number 2; complement of K_n has chromatic number n.
• K_n has chromatic number n-1; complement of K_n has chromatic number n-2.