Bipartite and Planar Graph Concepts

This lesson covers non-planar graphs, focusing on proving that the complete graph K5 and the bipartite graph K3,3 are not planar. Using Euler's formula, the lesson demonstrates proof by contradiction for both graphs, showing that they cannot be drawn without edges crossing. The K5 graph, with 5 vertices and 10 edges, and the K3,3 graph, with 6 vertices and 9 edges, both fail to satisfy the conditions for planarity, as shown through mathematical inequalities. The lesson concludes by reinforcing the understanding of non-planar graphs and their properties.

What is a planar graph?

• A graph with no vertices

• A graph with only one edge

• A graph that can be drawn with edges crossing

• A graph that can be drawn without any edges crossing

What is Euler's formula for planar graphs?

• v - e + f = 2

• v / e + f = 2

• v * e / f = 2

• v + e - f = 2

How many vertices and edges does the complete graph K5 have?

• 5 vertices and 10 edges

• 4 vertices and 8 edges

• 6 vertices and 10 edges

• 5 vertices and 9 edges

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

• 3f is less than 2e

• 3f is greater than 2e

• 2e is equal to 3f

• 2e is less than 3f

What is the relationship between edges and boundaries in a planar graph?

• Each edge is used as a boundary once

• Each edge is used as a boundary twice

• Each edge is used as a boundary three times

• Each edge is not used as a boundary

What is the smallest cycle in a bipartite graph like K3,3?

• A cycle with 2 edges

• A cycle with 4 edges

• A cycle with 3 edges

• A cycle with 5 edges

How many vertices and edges does the bipartite graph K3,3 have?

• 6 vertices and 9 edges

• 5 vertices and 10 edges

• 6 vertices and 10 edges

• 5 vertices and 9 edges

What is the contradiction found in the proof of K3,3's non-planarity?

• 2e is equal to 4f

• 2e is less than 4f

• 4f is less than 2e

• 4f is greater than 2e

Why can't K3,3 be drawn without edges crossing?

• It is a complete graph

• It is impossible to connect each house to each utility without crossing

• It has too few edges

• It has too many vertices

What is the significance of proving K3,3 is not planar?

• It solves the house and utilities problem

• It demonstrates that all graphs are planar

• It shows all bipartite graphs are non-planar

• It proves Euler's formula is incorrect