Lecture Five: Wagner's Theorem Every planar graph has a planar drawing constructed using just straight lines.

• Def - a max planar graph (mpg) is a planar graph such that the addition of any addtional edge makes the graph non-planar. Example: K5-{e}

• Prop - If G = (V,E) is mpg, V >= 3, then all regions are triangles

• Prop - If G = (V,E) is mpg, V >= 4, then all vertices have degree >= 3

• Prop - If G = (V,E) is mpg, then E = 3V-6

• Prop - If G = (V,E) is any planar graph, then at least one vertex has degree <= 5

• Prop - If G = (V,E) is mpg, V >= 4, then there are at least 4 vertices of degree <= 5.

Proof: Let pk = # of vertices of degree exactly k. Then: V = p3 + p4 + p5 +...; 2E = 3p3 + 4p4 + 5p5+...; add fact E = 3V=6, stir.

• Thm - Straight line drawings always possible.

Proof: Just work with mpgs. Induction on n = V. Base: n = 4. Induction step: If G has V = n+1, must have internal vertex of degree <=5. Delete it, add in a few arcs (maybe to make it new mpg, with n verts. Do line drawing of this. Find the "hole" you made by deletion (remove added marked edges).Then: just place deleted vert, hook it up( will always work, because at worst hole is a non-convex pentagon)

-- RobbieMoll - 21 Sep 2006