Discrete Math · Undergraduate

Planar Graphs and Euler's Formula V − E + F = 2

Quick answer

A graph is planar if it can be drawn in the plane with no edges crossing. Such a drawing splits the plane into faces, counting the outside, and for any connected planar drawing the numbers of vertices, edges and faces satisfy Euler's formula V − E + F = 2. Since every face needs at least three edges around it, a simple planar graph with at least 3 vertices has at most 3V − 6 edges. That bound rules out K₅, and the bound 2V − 4 for graphs with no triangles rules out K₃,₃.

What you'll learn

  • Decide whether a drawing is a plane drawing and count its faces
  • Prove and apply Euler's formula V − E + F = 2
  • Use E ≤ 3V − 6 and E ≤ 2V − 4 to rule out planarity
  • Check Euler's formula on the Platonic solids

Drawing without crossings

A graph is planar if it can be drawn in the plane with no two edges crossing. A drawing with crossings does not settle the question: the square with both diagonals, K4K_4, looks crossed, yet moving one vertex inside the triangle formed by the others removes every crossing.

A crossing-free drawing cuts the plane into regions called faces. The unbounded region outside the drawing counts as a face too.

K₄ drawn without crossings Four vertices: A, B and C form an outer triangle, and D sits inside it, joined to all three. Six edges, no crossings. The drawing has four faces: the three small triangles around D and the region outside. A B C D
K₄ drawn without crossings

Here V=4V = 4, E=6E = 6 and F=4F = 4: three inner triangles plus the outside. And 4−6+4=24 - 6 + 4 = 2.

Why V − E + F = 2

Build any connected plane drawing one edge at a time, keeping it connected. Start from a single vertex: V=1V = 1, E=0E = 0, F=1F = 1, and 1−0+1=21 - 0 + 1 = 2. Each new edge does one of two things.

  • It reaches a new vertex: VV and EE both rise by 11, and no face is split.
  • It joins two vertices already drawn: EE rises by 11, and the edge cuts one face in two, so FF rises by 11.

Either way V−E+FV - E + F does not change, so it stays 22. This is Euler’s formula.

The edge bound

In a simple graph with V≥3V \ge 3, every face is bounded by at least 33 edges, and each edge borders at most 22 faces. Counting edge-face contacts gives 3F≤2E3F \le 2E. Substituting F=2−V+EF = 2 - V + E:

3(2−V+E)≤2E⟹E≤3V−63(2 - V + E) \le 2E \quad\Longrightarrow\quad E \le 3V - 6

If the graph has no triangles, every face needs at least 44 edges, 4F≤2E4F \le 2E, and the same steps give E≤2V−4E \le 2V - 4.

Worked examples

Common mistakes

Practice problems

  1. A connected planar graph has 88 vertices and 1212 edges. How many faces does it have?

    Answer

    66

    Full solution

    F=2−8+12F = 2 - 8 + 12. This is the cube.

  2. What is the largest number of edges a simple planar graph on 66 vertices can have?

    Answer

    1212

    Full solution

    3⋅6−6=123 \cdot 6 - 6 = 12, reached by the octahedron.

  3. Check Euler’s formula for the tetrahedron and the octahedron.

    Answer

    4−6+4=24 - 6 + 4 = 2 and 6−12+8=26 - 12 + 8 = 2

    Full solution

    The tetrahedron has 44 corners, 66 edges and 44 faces; the octahedron has 66, 1212 and 88.

  4. A connected planar graph has 77 faces and 1212 edges. How many vertices?

    Answer

    77

    Full solution

    V=2+E−F=2+12−7V = 2 + E - F = 2 + 12 - 7.

  5. A plane drawing has 1212 vertices and every face is a triangle. Find EE and FF.

    Answer

    E=30E = 30, F=20F = 20

    Full solution

    With all faces triangles, 3F=2E3F = 2E and the bound is reached: E=3⋅12−6=30E = 3 \cdot 12 - 6 = 30, so F=2−12+30F = 2 - 12 + 30. This is the icosahedron.

  6. A connected planar graph has every vertex of degree 33 and 1212 faces. Find VV and EE.

    Answer

    V=20V = 20, E=30E = 30

    Full solution

    The handshaking lemma gives 3V=2E3V = 2E. Then V−3V2+12=2V - \tfrac{3V}{2} + 12 = 2, so V=20V = 20. This is the dodecahedron.

  7. Can a simple planar graph have 77 vertices and 1616 edges?

    Answer

    No

    Full solution

    3⋅7−6=15<163 \cdot 7 - 6 = 15 < 16.

  8. A student says K3,3K_{3,3} is planar because 9≤3⋅6−69 \le 3 \cdot 6 - 6. What is wrong?

    Answer

    The bound is necessary, not sufficient; the sharper bound 2V−4=82V - 4 = 8 applies and fails.

    Full solution

    K3,3K_{3,3} has no triangles, so each face needs 44 edges and E≤8E \le 8. With 99 edges it is not planar.

Frequently asked questions

What is a planar graph?

A graph that can be drawn in the plane with no two edges crossing. A graph drawn with crossings may still be planar if some other drawing avoids them.

What is Euler's formula for planar graphs?

For a connected graph drawn in the plane without crossings, V − E + F = 2, where F counts the faces including the outer one.

How do you show a graph is not planar?

Use a counting bound. A simple planar graph with V ≥ 3 has E ≤ 3V − 6; with no triangles, E ≤ 2V − 4. A graph with more edges cannot be planar.

Why are K₅ and K₃,₃ not planar?

K₅ has 10 edges but 3(5) − 6 = 9. K₃,₃ has no triangles and 9 edges, but 2(6) − 4 = 8.

What does Euler's formula say about polyhedra?

The corners and edges of a convex polyhedron form a planar graph, so V − E + F = 2. A cube has 8 − 12 + 6 = 2.

What to learn next