Graph Theory Concepts and Properties

The video demonstrates that the complete graph K5 and the complete bipartite graph K3,3 are non-planar. It uses edge bounds to prove the non-planarity of K5 and introduces a lemma for planar graphs without triangles to prove the non-planarity of K3,3. The video concludes by hinting at Kuratowski's theorem, which identifies forbidden subgraphs for planar graphs.

What is the main objective of the video?

• To prove that K5 and K3,3 are planar

• To introduce Euler's formula

• To prove that K5 and K3,3 are not planar

• To discuss the properties of bipartite graphs

What is the edge bound for a maximal planar graph with n vertices?

• 3n - 6

• 4n - 8

• 2n - 4

• n^2 - n

How many edges does the complete graph K5 have?

• 10

• 5

• 15

• 20

What is the condition for a graph to be planar according to the edge bound?

• The number of edges must be less than or equal to 2n - 4

• The number of edges must be exactly 3n - 6

• The number of edges must be greater than 3n - 6

• The number of edges must be less than or equal to 3n - 6

What additional condition is considered for the new edge bound?

• The graph must have even cycles

• The graph must be complete

• The graph must have no triangles

• The graph must be bipartite

What is the new edge bound for a planar graph with no triangles?

• 3n - 6

• 2n - 4

• 4n - 8

• n^2 - n

How many vertices and edges does K3,3 have?

• 5 vertices and 9 edges

• 6 vertices and 12 edges

• 5 vertices and 10 edges

• 6 vertices and 9 edges

Why can't K3,3 be planar according to the new edge bound?

• It has more than 8 edges

• It has more than 10 edges

• It has more than 12 edges

• It has more than 6 edges

What is the significance of K5 and K3,3 in graph theory?

• They are the largest planar graphs

• They are examples of bipartite graphs

• They are the only forbidden subgraphs for planarity

• They are examples of planar graphs