Course contentsShow
← Mathematics
Lesson 2692 of 3,12153. Graph TheoryFree lesson

Consequences of Euler's Formula

Derive inequalities bounding edges in planar graphs: E ≤ 3V - 6 for simple planar graphs.

Consequences of Euler's Formula

What You'll Learn

You'll learn how to derive the fundamental edge inequality E ≤ 3V - 6 that every simple planar graph must satisfy.

The Core Idea

Euler's formula (V - E + F = 2) gave us a beautiful relationship connecting vertices, edges, and faces. Now we'll squeeze even more information out of it to discover a powerful upper bound on how many edges a planar graph can have.

Think of it like a building code: just as zoning laws limit how tall buildings can be based on their footprint, planarity imposes strict limits on how "dense" with edges a graph can be given its number of vertices.

Deriving E ≤ 3V - 6

Start with a simple planar graph (no loops, no multiple edges) having at least 3 vertices. Every face must be bounded by at least 3 edges. If we count edge-face incidences, each edge borders exactly 2 faces, giving us:

2E ≥ 3F

Why? The sum of all face boundaries counts each edge twice (once from each side), and this sum must be at least 3F since each face needs at least 3 edges.

Rearranging: F ≤ 2E/3

Now substitute into Euler's formula:

  • V - E + F = 2
  • V - E + (something ≤ 2E/3) ≤ 2
  • V - E + 2E/3 ≤ 2
  • V - E/3 ≤ 2
  • V - 2 ≤ E/3
  • E ≤ 3V - 6

This inequality is sharp: some planar graphs (like K₄, the complete graph on 4 vertices) achieve it exactly!

Applications

This immediately proves K₅ isn't planar: it has V = 5, E = 10, but 3(5) - 6 = 9 < 10. Busted!

Key Takeaway: Every simple planar graph with V ≥ 3 satisfies E ≤ 3V - 6, giving us a quick planarity test by counting vertices and edges alone.