Back to the on-screen lesson ·
Euler's formula for a plane drawing, the edge bound that follows from counting incidences two ways, and the odd cycle that decides whether a graph is bipartite.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to use Euler's formula to find the faces of a plane drawing, derive the bound of three vertices less six on the edges of a planar graph by counting face-edge incidences two ways, and use that bound to prove a graph is not planar without attempting a single drawing. You will also be able to decide whether a graph is bipartite by hunting for a cycle of odd length, apply the tighter bound that bipartiteness gives, and say why staying within a bound proves nothing.
Unit 4's habit of counting one set two ways, and lesson 20's handshake lemma, which is that habit applied to vertices and edges. This lesson applies it again to edges and faces, and the result is a bound that decides which graphs can be drawn without crossings.
A graph is planar when it can be drawn in the plane with no two edges crossing; such a drawing is a plane drawing, and its faces are the regions it cuts the plane into, the unbounded outer region included. A graph is bipartite when its vertices split into two groups with every edge running between the groups. $K_n$ is the complete graph on $n$ vertices and $K_{m,n}$ the complete bipartite graph.
Euler's formula. For any connected plane drawing,
$$V - E + F = 2.$$
The surprising part is that $F$ does not depend on the drawing. Two people drawing the same planar graph in completely different ways get the same number of regions, because $V$ and $E$ are properties of the graph and the formula fixes $F$ from them.
The bound. Count the pairs (a face, an edge on its boundary), two ways — unit 4's technique, in a new setting. By face: each face needs at least three edges round it, so the total is at least $3F$. By edge: each edge borders exactly two faces, so the total is exactly $2E$. Hence $2E \ge 3F$, and substituting $F = 2 - V + E$ gives
$$E \le 3V - 6.$$
That single inequality settles $K_5$: five vertices allow at most nine edges, and $K_5$ has ten. $K_5$ is not planar, proved by arithmetic rather than by trying drawings — which matters, because no number of failed drawings would prove anything.
Bipartite graphs. A graph is bipartite exactly when it has no cycle of odd length. One direction is easy: colour the two groups, and a cycle alternates colours, so it must have even length. The other direction is the useful one: given no odd cycle, colour each vertex by the parity of its distance from a fixed start, and check no edge joins two of the same colour.
For bipartite planar graphs the bound tightens to $E \le 2V - 4$, because every face now needs at least four edges — the three-edge face would be a triangle, which is an odd cycle. That settles $K_{3,3}$: six vertices allow at most eight edges and it has nine. The three-utilities puzzle has no solution, and again the proof is arithmetic.
Another way: steps
To decide whether a graph is planar:
Another way: picture
A cube drawn flat, as a small square inside a large one with the corners joined. Eight vertices, twelve edges, and six regions — four between the squares, one inside the small square, and the outside. $8 - 12 + 6 = 2$, and the outer region is the one people forget.
| Graph | $V$ | $E$ | $3V - 6$ | Verdict |
|---|---|---|---|---|
| $K_4$ | $4$ | $6$ | $6$ | within the bound; and it is planar |
| $K_5$ | $5$ | $10$ | $9$ | over; not planar |
| $K_{3,3}$ | $6$ | $9$ | $12$ | within; but bipartite, so the bound is $2V-4 = 8$ — not planar |
| the cube | $8$ | $12$ | $18$ | within; and it is planar |
The bound is a one-way test. Exceeding it proves a graph is not planar; staying within it proves nothing at all, as $K_{3,3}$ shows — it passes the general bound and fails the bipartite one.
What does decide the question in general is Kuratowski's theorem: a graph is planar exactly when it contains no copy of $K_5$ or $K_{3,3}$, allowing edges to be subdivided. This course states it and does not prove it; what it wants you to take is the shape of the situation — a cheap necessary condition that often settles matters, and a hard characterisation behind it.
Forgetting the outer face. $V - E + F = 2$ counts the unbounded region. Without it every answer is one short.
Using the bound backwards. $E \le 3V - 6$ being satisfied does not make a graph planar.
Applying Euler's formula to a disconnected drawing. For $c$ pieces it is $V - E + F = 1 + c$.
Concluding non-planarity from failed drawings. Not finding a crossing-free drawing is not a proof; the arithmetic is.
Using the bipartite bound on a graph that is not bipartite. Check for an odd cycle first.
A graph handed to you with edges crossing may still be planar — the crossings belong to that drawing and not to the graph. $K_4$ is usually drawn as a square with both diagonals, which has one crossing, and it is planar: redraw it as a triangle with a vertex in the middle. So a picture with crossings is no evidence at all, in either direction, and the question is always whether some drawing avoids them. That is why the edge bound matters: it is a statement about the graph, and no drawing can argue with it.
$K_5$ has five vertices and, being complete, $\binom{5}{2} = 10$ edges.
Count $V$ and $E$ first.
A planar graph on five vertices may have at most $3 \times 5 - 6 = 9$ edges.
Apply the bound.
Ten exceeds nine, so $K_5$ cannot be drawn in the plane without a crossing. No drawing was attempted, and the conclusion covers every possible drawing at once.
One inequality rules out infinitely many attempts.
Three houses, three utilities, every house joined to every utility: that is $K_{3,3}$, with $6$ vertices and $9$ edges.
Model the puzzle as a graph.
The general bound gives $3 \times 6 - 6 = 12$, which $9$ does not exceed — so it says nothing.
The cheap test fails to decide.
But the graph is bipartite, so every face needs at least four edges and the bound tightens to $2 \times 6 - 4 = 8$. Nine exceeds eight, so the puzzle has no solution.
The right bound is the one that uses what you know.
Euler's formula: $F = 2 - V + E = 2 - 7 + 9 = 4$, counting the outer region.
Rearrange and substitute.
The bound: $3 \times 7 - 6 = 15$, and $9$ is comfortably within it.
The bound is necessary, not sufficient.
So four faces, and the edge count raises no objection. Note what has and has not been established: the graph was given as drawn without crossings, so planarity was never in question here — the bound was only a consistency check, and a graph passing it might still not have been drawable at all.
the complete graph on four vertices is drawn in the plane with $4$ vertices and $6$ edges, no two edges crossing. Fill in the table.
| Number | |
|---|---|
| Faces of the drawing | |
| Most edges a planar graph on these vertices could have |
A connected planar graph is drawn with $9$ vertices and $11$ edges. How many faces does the drawing have?
Answer:
At most how many edges can a simple planar graph on $4$ vertices have?
Answer:
Match each graph to whether its vertices can be split into two groups with every edge running between the groups.
| Bipartite — it has no cycle of odd length | Not bipartite — it contains a cycle of odd length | |
|---|---|---|
| A square, its four corners joined in a cycle | ||
| A triangle | ||
| Any tree | ||
| The complete graph on four vertices |
Build the derivation of $E \le 3V - 6$ for a simple connected planar graph with at least three vertices.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
a five-vertex planar graph is drawn in the plane with $5$ vertices and $8$ edges, no two edges crossing. Fill in the table.
| Number | |
|---|---|
| Faces of the drawing | |
| Most edges a planar graph on these vertices could have |
You can find faces with Euler's formula, derive and apply the edge bound, and test a graph for bipartiteness. Say in your own words why the face count does not depend on the drawing, and why the edge bound can prove non-planarity but never planarity. Next: divisibility, the division algorithm, and the primes that every integer is built from.
10. Your turn: a connected planar graph is drawn with $7$ vertices and $9$ edges. How many faces, and is the edge count within the bound?, step 3