Faces and Euler's Formula

Draw a triangle. How many vertices, edges and regions does it have? Be careful with the regions: you have cut the page into the inside and the outside, so there are two, not one.

In any planar drawing of a connected graph, the number of vertices, edges and faces satisfies one equation. Faces are the regions the drawing cuts the plane into, and the unbounded region outside the whole drawing is one of them.

Take a planar drawing, one with no crossings, and imagine cutting the page along every edge. The page falls into pieces, and each piece is a face.

A triangle drawn on a page has two faces: the region inside it and the region outside. A single edge joining two dots has one face, the whole page, because a single line does not enclose anything.

Faces exist only for planar drawings. If edges cross, the regions are not well defined, because a crossing is not a vertex and the pieces do not separate cleanly. So the first step in any face-counting question is to check the drawing has no crossings, and redraw it if it has.

The number of faces turns out not to depend on which crossing-free drawing you use. Different planar drawings of the same graph can look very different and always have the same number of faces, which is one of the things Euler's formula tells you.

The region outside the whole drawing is a face. It is called the outer face or the unbounded face, and it counts.

This is the single most common error in the topic, and it has a recognisable symptom: the formula gives $1$ instead of $2$. If that happens, count again and include the outside.

There is a good reason it feels wrong. The other faces are enclosed and look like regions; the outer one stretches away forever and looks like empty page. But it is bounded by the outer edges of the drawing in exactly the way the inner faces are bounded by theirs.

A helpful way to see it: imagine the drawing on the surface of a ball rather than a flat page. Then no face is special and no face is infinite, and the outside face is simply the one on the far side. Flattening the ball onto paper is what makes one of the faces look different from the others.

For any planar drawing of a connected graph, with $v$ vertices, $e$ edges and $f$ faces:

$v - e + f = 2$

Check it on the diagram above, which has $4$ vertices, $6$ edges and $4$ faces, three inside and one outside:

$4 - 6 + 4 = 2$

Check it on a triangle: $3$ vertices, $3$ edges, and $2$ faces, giving $3 - 3 + 2 = 2$.

Check it on a single edge joining two dots: $2$ vertices, $1$ edge, $1$ face, giving $2 - 1 + 1 = 2$.

Both conditions are needed. The drawing must be planar, or faces are not defined. The graph must be connected, or the answer changes: a graph in two separate pieces gives $3$, and in general a graph in $k$ pieces gives $k + 1$.

Because the three numbers are locked together, any two of them determine the third.

A connected planar graph with $8$ vertices and $13$ edges has

$f = 2 - v + e = 2 - 8 + 13 = 7$

faces, and you can say so without seeing the drawing at all. Rearranged the other ways, $v = 2 + e - f$ and $e = v + f - 2$.

Two habits make these reliable. Rearrange the formula symbolically before substituting, rather than juggling numbers. And sanity-check the answer: the face count of a connected planar graph is at least $1$, and $f = 1$ happens exactly when the graph has no cycles at all.

Check the word connected appears in the question before using the formula. Without it the value on the right-hand side is unknown and nothing can be computed.

Lesson 4 left a gap: how do you prove that no drawing avoids crossings? Euler's formula closes it.

For a simple connected planar graph with at least $3$ vertices, the formula leads to

$e \leq 3v - 6$

The stretch task derives this. Its power is that it mentions no drawing at all, only the two counts, so it applies to every possible drawing at once.

Apply it to the complete graph on five vertices, which has $v = 5$ and $e = 10$:

$3v - 6 = 3(5) - 6 = 9$, and $10 > 9$.

The inequality fails, so no planar drawing of this graph can exist. That is a proof of non-planarity, not a failed search, and it took two lines.

One caution. The inequality is necessary for planarity, not sufficient. A graph satisfying $e \leq 3v - 6$ may still be non-planar, and the three-utilities graph, with $v = 6$ and $e = 9$ against a bound of $12$, is exactly such a case. Passing the test proves nothing; failing it proves non-planarity.

Five items on faces and Euler's formula. All graphs are connected and all drawings are planar.

1. 1 A triangle is drawn on a page. How many faces does it have?

   Show answer
   Inside and outside.$2$

2. 2 A connected planar graph has $10$ vertices and $15$ edges. How many faces?

   Show answer
   $f = 2 - v + e$$7$

3. 3 A connected planar drawing has $7$ vertices and $5$ faces. How many edges?

   Show answer
   $e = v + f - 2$$10$

4. 4 A connected planar drawing has $12$ edges and $6$ faces. How many vertices?

   Show answer
   $v = 2 + e - f$$8$

5. 5 A student computes $v - e + f$ and gets $1$. What have they most likely done?

   Show answer
   The outer region is a face.Forgotten the outer face