Graph Theory: Planarity Concepts

The video tutorial discusses Kuratowski's theorem, focusing on the non-planarity of K5 and K33 graphs. It provides detailed proofs for the non-planarity of these graphs, explaining the assumptions and contradictions involved. The concept of outer planar graphs is introduced, with examples illustrating their properties. The tutorial also covers maximal outer planar graphs, including a theorem that states such graphs have p-2 interior faces, with a proof using mathematical induction.

What is the significance of Kuratowski's Theorem in graph theory?

• It identifies planar graphs.

• It provides a method to color graphs.

• It determines the shortest path in graphs.

• It characterizes non-planar graphs.

Which of the following graphs is non-planar according to Kuratowski's Theorem?

• K4

• K5

• K2,3

• K1,1

What assumption is made to prove K5 is non-planar?

• K5 is a cycle.

• K5 is bipartite.

• K5 is planar.

• K5 is a tree.

Which formula is used in the proof of K5's non-planarity?

• Pythagorean theorem

• Bayes' theorem

• Fermat's Last Theorem

• Euler's formula

What is the contradiction found in the proof of K5's non-planarity?

• 10 is less than or equal to 9

• 5 is greater than 6

• 3 is equal to 4

• 7 is less than 8

What is assumed about K33 in its non-planarity proof?

• K33 is a tree.

• K33 is planar.

• K33 is a cycle.

• K33 is bipartite.

What property of planar graphs is used in the proof of K33's non-planarity?

• They have no cycles.

• They have no edges.

• They are triangle-free.

• They have no vertices.

What is an outer planar graph?

• A graph with no vertices.

• A graph with all edges inside the region.

• A graph with all vertices on the boundary of the exterior region.

• A graph with no edges.

Which of the following is an example of an outer planar graph?

• K5

• K4

• A cycle graph

• A complete graph

What makes a graph non-outer planar?

• All edges are straight.

• Some vertices lie inside the interior region.

• All vertices are connected.

• All vertices lie on the boundary.