Euler's Formula (Euler's Theorem)

Definition

• A connected planar graph G with
  • |v| vertices
  • |e| edges
• Has exactly |e| - |v| + 2 regions.
• Applicable only to connected planar graphs.

Key Concepts

Connected Graph

• A graph where there is a path (edge) from any vertex to every other vertex.
  • Example:
    • Vertex connections:
      • p to q, v to u, q to r, s to r.
    • Vertex z is isolated (no edges), making the graph not connected.

Planar Graph

• A graph that can be drawn on a plane without edge crossings.
  • Example:
    • Graph with crossing edges is not planar, while non-crossing edges make it planar.

Regions

• A region is defined as a cycle that forms a boundary.
• Formula for calculating the number of regions:
  • |r| = |e| - |v| + 2
  • Rearranged:
  • |v| - |e| + |r| = 2

Examples

Example 1: Verify Euler's Theorem

1. Given a graph:
   • Count vertices:
     • Total = 8
   • Count edges:
     • Total = 10
2. Apply the formula for regions:
   • |r| = |e| - |v| + 2
   • |r| = 10 - 8 + 2 = 4
3. Confirm the regions:
   • R1: Cycle p-q-u-v-p (4 edges)
   • R2: Following edges q-r-w-t-u-q (6 edges)
   • R3: Cycle r-s-t (3 edges)
   • R4: Outer region (also confirmed as 4).
4. Verify Euler's formula:
   • |v| - |e| + |r| = 2
   • 8 - 10 + 4 = 2 (verified).

Example 2: Determine Degrees and Verify Euler's Formula

1. Count vertices and edges:
   • |v| = 7
   • |e| = 9
2. Calculate regions:
   • |r| = |e| - |v| + 2
   • |r| = 9 - 7 + 2 = 4
3. Determine degrees of each region:
   • R1: 3 edges
   • R2: 5 edges
   • R3: 3 edges
   • R4: 7 edges
4. Calculate sum of degrees:
   • Total = 3 + 5 + 3 + 7 = 18
   • Confirmed as twice the number of edges: 9 edges x 2 = 18.
5. Verify Euler's formula:
   • |v| - |e| + |r| = 2
   • 7 - 9 + 4 = 2 (verified).

Conclusion

• Euler's formula is validated through both examples.
• Understanding connected and planar graphs is crucial for applying Euler's theorem.