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, , 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.
Here , and : three inner triangles plus the outside. And .
Why V − E + F = 2
Build any connected plane drawing one edge at a time, keeping it connected. Start from a single vertex: , , , and . Each new edge does one of two things.
- It reaches a new vertex: and both rise by , and no face is split.
- It joins two vertices already drawn: rises by , and the edge cuts one face in two, so rises by .
Either way does not change, so it stays . This is Euler’s formula.
The edge bound
In a simple graph with , every face is bounded by at least edges, and each edge borders at most faces. Counting edge-face contacts gives . Substituting :
If the graph has no triangles, every face needs at least edges, , and the same steps give .
Worked examples
Common mistakes
Practice problems
-
A connected planar graph has vertices and edges. How many faces does it have?
Answer
Full solution
. This is the cube.
-
What is the largest number of edges a simple planar graph on vertices can have?
Answer
Full solution
, reached by the octahedron.
-
Check Euler’s formula for the tetrahedron and the octahedron.
Answer
and
Full solution
The tetrahedron has corners, edges and faces; the octahedron has , and .
-
A connected planar graph has faces and edges. How many vertices?
Answer
Full solution
.
-
A plane drawing has vertices and every face is a triangle. Find and .
Answer
,
Full solution
With all faces triangles, and the bound is reached: , so . This is the icosahedron.
-
A connected planar graph has every vertex of degree and faces. Find and .
Answer
,
Full solution
The handshaking lemma gives . Then , so . This is the dodecahedron.
-
Can a simple planar graph have vertices and edges?
Answer
No
Full solution
.
-
A student says is planar because . What is wrong?
Answer
The bound is necessary, not sufficient; the sharper bound applies and fails.
Full solution
has no triangles, so each face needs edges and . With 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.