More on planar graphs (graph theory day 6)

Main Ideas

A planar graph is a graph that can be drawn so that its edges do not cross. It has:

• Vertices: Points in the graph.
• Edges: Connections between vertices. A loop counts as one edge.
• Faces: Regions formed by the edges, including the region outside the graph.

Counting Examples

• For the complete graph (K_4), (V=4), (E=6), and (F=4), counting the outside region as a face.
• For a triangle with a loop at one vertex, (V=3), (E=4), and (F=3). The faces are the triangle’s interior, the loop’s interior, and the outside region.

Euler’s Formula

For a planar graph,

[ V - E + F = 2 ]

Equivalently,

[ V + F = E + 2 ]

The lesson checks that this relationship holds for the examples, including one with (20) vertices, (30) edges, and (12) faces.

Dual Graphs

To create the dual of a planar graph:

1. Make one vertex for each face of the original graph, including the outside face.
2. Connect two dual vertices with an edge when their corresponding faces share a border.

The dual of a planar graph is also planar. The lesson ends by asking students to explore how the numbers of vertices, edges, and faces in a planar graph relate to those in its dual.

Speaker and Source

• Speaker: The lesson’s instructor, identified by the video context as Dr. Ford.
• Other speakers or sources: None featured.