A planar graph can be drawn with no edges crossing. For a connected planar drawing, V−E+F=2, and a simple planar graph with at least 3 vertices has E≤3V−6
about 30 min1 simulation1 practice question1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
use Euler's formula and the edge bounds of planar graphs;
find the chromatic number of small graphs and use the greedy bound;
prove R(3,3)=6 and use the idea in counting problems.
Planar graphs and Euler's formula
A graph is planar when it can be drawn in the plane with no two edges crossing. Such a drawing cuts the plane into faces, and the outside counts as one face.
Euler's formula. For a connected planar drawing with V vertices, E edges and F faces,
V−E+F=2.
Why. For a tree, E=V−1 and F=1, so the formula holds. If the graph has a cycle, remove one edge of that cycle. The two faces on either side of it merge, so E and F both drop by 1 and V−E+F stays the same. Repeat until a tree is left.
A cube has V=8, E=12 and F=6, and indeed 8−12+6=2.
How many edges a planar graph can have
In a simple planar graph with V≥3, every face has at least 3 edges on its border, and every edge borders at most 2 faces. So 3F≤2E. Put this into Euler's formula:
E≤3V−6.
If the graph has no triangle, every face has at least 4 edges, so 4F≤2E and E≤2V−4.
Two graphs that are not planar.
K5 has V=5 and E=10, but 3V−6=9.
K3,3 has no triangle, V=6 and E=9, but 2V−4=8.
So neither can be drawn without crossings. This is the old puzzle of joining three houses to three utilities. Kuratowski's theorem says more: a graph is planar exactly when it contains no copy of K5 or K3,3, with edges allowed to be split by extra vertices.
Three graphs. On the left, K4 drawn without crossings as a triangle with a centre point joined to its corners; its four faces are shaded, the outside face included. In the middle, K5 drawn as a pentagon with its five diagonals; the diagonals cross. On the right, K3,3 with three houses on top and three wells below, every house joined to every well; some lines cross.
Colouring
Exams that share a student must not be held at the same time. Draw a vertex for each exam and an edge between two exams that share a student. A colouring gives every vertex a colour so that joined vertices get different colours. The colours are the time slots. The fewest colours needed is the chromatic numberχ(G), read "chi of G".
χ(Kn)=n, because every two vertices are joined.
χ(G)≤2 exactly when G is bipartite.
An odd cycle needs 3 colours.
Greedy bound. Colour the vertices one at a time with the first free colour. A vertex has at most Δ neighbours, so χ(G)≤Δ+1, where Δ is the largest degree.
For planar graphs, E≤3V−6 gives an average degree below 6, so some vertex has degree at most 5. Remove it, colour the rest by induction, and put it back with one of 6 colours: every planar graph can be coloured with 6 colours. The four colour theorem (Appel and Haken, 1976, with a computer check) says that 4 colours always suffice.
Ramsey numbers
Among any 6 people, there are always 3 who all know each other or 3 who are all strangers to each other.
Proof. Draw K6 and colour an edge red for "know each other" and blue for "strangers". Pick a person P. Of the 5 edges at P, at least 3 have the same colour by the pigeonhole principle, say red, to A, B and C.
If any edge among A, B, C is red, it forms a red triangle with P.
If none is red, then A, B, C form a blue triangle.
Five people are not enough. Colour the 5 sides of a pentagon red and its 5 diagonals blue. The red edges form a 5-cycle and the blue edges form another 5-cycle, a star shape, and neither has a triangle.
The Ramsey numberR(3,3) is the smallest n such that every red and blue colouring of Kn has a one-colour triangle. We have shown R(3,3)=6.
Five points at the corners of a regular pentagon. The five sides of the pentagon are red and the five diagonals, which form a five-pointed star, are blue. No three points are joined by three edges of one colour.
With three colours the same argument works. A vertex of K17 has 16 edges, so at least 6 share a colour. Among those 6 neighbours, an edge of that colour makes a triangle, and otherwise two colours are left on K6. So R(3,3,3)≤17, and in fact R(3,3,3)=17. Larger Ramsey numbers are very hard: R(4,4)=18, but R(5,5) is still unknown.
Practise with new numbers
Try it in Python
The program checks every red and blue colouring of K5 and of K6, and counts the colourings with no one-colour triangle.
Common mistakes
Forgetting the outside face. It counts in F.
Using E≤3V−6 for a graph with no triangle. Then the sharper E≤2V−4 holds.
A bound is not a proof of planarity.E≤3V−6 can hold for a graph that is still not planar.
The greedy bound is not exact. A star has Δ large but χ=2.
Remember these
Connected planar drawing: V−E+F=2.
Simple planar, V≥3: E≤3V−6; no triangle: E≤2V−4. K5 and K3,3 are not planar.
χ(Kn)=n; bipartite means χ≤2; odd cycle needs 3; χ≤Δ+1.
R(3,3)=6 and R(3,3,3)=17.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
A connected planar graph has 8 vertices and 13 edges. How many faces does its drawing have?
Can a simple planar graph have 7 vertices and 16 edges?
What is the chromatic number of the cycle C9?
A graph has largest degree 4. What does the greedy bound say about its chromatic number?
Why does the proof of R(3,3)≤6 fail for 5 people?
References
D. B. West, Introduction to Graph Theory, Chapter 5 (colouring) and Chapter 6 (planar graphs).
R. J. Wilson, Introduction to Graph Theory, Chapters 5 and 6.
R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, Chapter 1.
Enroll free in Graph Theory
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.