10.1 Planar graph properties and Euler's formula

Planar graphs are a fascinating subset of graphs that can be drawn without edge crossings. They have unique properties, like Euler's formula and maximum edge limits, that set them apart from other graph types.

Understanding planar graphs is crucial for real-world applications. From circuit design to map coloring, these concepts help solve complex problems. Kuratowski's theorem provides a powerful tool for determining graph planarity.

Planar Graphs and Their Properties

Properties of planar graphs

• Planar graphs drawn on plane without edge crossings edges intersect only at vertices
• Every planar graph has planar embedding subgraphs also planar
• Maximum edges in planar graph with n vertices: $3n - 6$ (for $n \geq 3$)
• Every planar graph 4-colorable (Four Color Theorem)
• Dual graphs constructed by placing vertex in each face of original planar graph edges correspond to adjacent faces

Faces in planar graphs

• Faces regions bounded by edges in planar embedding include outer (infinite) face
• Each face bounded by cycle of edges degree of face number of surrounding edges
• Connected planar graph faces simply connected disconnected graphs may have faces with holes

Euler's Formula and Graph Planarity

Applications of Euler's formula

• Euler's formula for planar graphs: $V - E + F = 2$ (V vertices, E edges, F faces)
• Determine number of faces in planar graph
• Calculate maximum edges in planar graph
• Prove non-planarity of certain graphs ($K_5$ and $K_{3,3}$)
• Variations for graphs on other surfaces (torus) and multiple connected components

Kuratowski's theorem for planarity

• Graph planar if and only if no subgraph homeomorphic to $K_5$ or $K_{3,3}$
• Homeomorphism graphs obtained by inserting or removing degree 2 vertices
• Identify $K_5$ or $K_{3,3}$ subdivisions in graph to prove non-planarity
• Wagner's theorem equivalent formulation using graph minors instead of homeomorphism