Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 36 Β· Planarity and Flows

Planar Graphs and Euler's Formula

Learn what makes a graph planar, trace faces of an embedding in Python, prove edge bounds from Euler's formula and see why planar graphs are 6-colorable.

Can you draw a graph on a sheet of paper without any edges crossing? A road map, a printed circuit and a subway diagram all hope the answer is yes. A graph that can be drawn in the plane with no crossings is called planar, and the drawing itself is a plane graph or planar embedding. Planarity looks like a drawing puzzle, but it is governed by a clean counting formula and a famous characterization that you will see in the next lesson.

Faces and Euler's formula

A plane graph divides the plane into regions called faces. One of them, the unbounded outer region, counts as a face too. For example, a triangle has two faces: the inside and the outside.

Euler's formula. For a connected plane graph with V vertices, E edges and F faces: V βˆ’ E + F = 2.

Why? A tree has E = V βˆ’ 1 edges and a single face, so V βˆ’ (Vβˆ’1) + 1 = 2. Every extra edge you add to a connected graph closes a cycle and splits one face into two, raising E and F by one each, so the value stays 2. For a graph with c components the formula becomes V βˆ’ E + F = 1 + c.

The most important consequence concerns edge counts. Every face is bounded by at least 3 edge-sides (in a simple graph with at least 3 vertices), and each edge borders at most 2 faces, so 3F ≀ 2E. Substituting into Euler's formula gives:

  • E ≀ 3V βˆ’ 6 for every simple planar graph with V β‰₯ 3.
  • E ≀ 2V βˆ’ 4 if the graph is also triangle-free (e.g., bipartite), since each face then has at least 4 sides.

These inequalities immediately show that some graphs are not planar: K5 has V = 5 and E = 10 > 3Β·5 βˆ’ 6 = 9, and K3,3 is bipartite with V = 6 and E = 9 > 2Β·6 βˆ’ 4 = 8.

Euler's formula

V Vertices
E Edges
F Faces, outer one included

V βˆ’ E + F = 2 for connected plane graphs

1 / 2

Tracing faces in code

To count faces in a program, give each vertex a rotation: its neighbors in order around the vertex (here, by angle from the vertex coordinates). A face is then found by walking along half-edges: arriving at v from u, turn to the neighbor just before u in v's rotation and continue until you return to where you started. Every half-edge belongs to exactly one face, so counting the walks counts the faces.

The same procedure applied to a drawing with crossings treats a crossing as if it were a normal embedding, and gives a face count that violates Euler's formula, which is a neat way to detect it.

Python Count faces of a drawing and test Euler's formula

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two genuine embeddings give exactly 2. The crossing drawing of K5 does not, because the face-tracing walk pretends the crossing points are not there, so it is not describing a valid plane graph.

Python Test the edge bounds that rule out planarity

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Careful with the direction of the logic: violating the bound proves non-planarity, but passing it proves nothing. The Petersen graph passes (15 ≀ 24) yet is not planar, which is explained by Kuratowski's theorem.

Planar graphs have a low-degree vertex

Summing degrees gives 2E ≀ 6V βˆ’ 12, so the average degree is below 6. Hence every planar graph has a vertex of degree at most 5. Remove that vertex, which leaves another planar graph with the same property, and repeat. In other words, planar graphs have degeneracy at most 5, and the smallest-last greedy coloring from greedy coloring uses at most 6 colors. Heawood's refinement shows 5 colors always suffice, and the celebrated Four Color Theorem (Appel and Haken, 1976, first proved with a computer) says 4 suffice.

Python Six-color a triangulated grid with smallest-last

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dual graph

Given a plane graph G, its dual G* has one vertex per face of G, and for every edge of G an edge joining the two faces on its sides. Duals turn vertices into faces and faces into vertices, so V* = F, E* = E, F* = V, and Euler's formula is symmetric. Coloring the faces of a map so that neighboring countries differ is the same as coloring the vertices of the dual, which is why the Four Color Theorem is usually stated for maps.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. A connected plane graph has 8 vertices and 12 edges. How many faces does it have?

    Euler's formula gives F = 2 βˆ’ V + E = 2 βˆ’ 8 + 12 = 6.
  2. 2. A simple planar graph with V >= 3 vertices has at most how many edges?

    Every face has at least three sides, so 3F ≀ 2E; combined with Euler's formula this gives E ≀ 3V βˆ’ 6.
  3. 3. If a graph satisfies E ≀ 3V βˆ’ 6, what can you conclude?

    The inequality can prove non-planarity when violated, but graphs such as the Petersen graph satisfy it and are still not planar.
  4. 4. Why does every planar graph have a vertex of degree at most 5?

    From E ≀ 3V βˆ’ 6 we get that the degree sum 2E is less than 6V, so some vertex has degree at most 5.

Summary

  • A planar graph can be drawn without crossings; the regions of such a drawing are faces, including the outer one.
  • Euler's formula: V βˆ’ E + F = 2 for connected plane graphs (V βˆ’ E + F = 1 + c with c components).
  • Simple planar graphs have E ≀ 3V βˆ’ 6 (E ≀ 2V βˆ’ 4 when triangle-free), which shows K5 and K3,3 are not planar.
  • Planar graphs always have a vertex of degree ≀ 5, so six colors suffice by greedy coloring; five colors and the Four Color Theorem sharpen this.
  • The dual graph swaps vertices and faces.

Next: Kuratowski's Theorem and Planarity Checking