HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers
  1. Mathematics
  2. /Graph Theory
  3. /Planar graphs, colouring and Ramsey numbers

Course 30.3·Lesson 3 of 3

Planar graphs, colouring and Ramsey numbers

A planar graph can be drawn with no edges crossing. For a connected planar drawing, V−E+F=2V - E + F = 2V−E+F=2, and a simple planar graph with at least 333 vertices has E≤3V−6E \le 3V - 6E≤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
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers

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)=6R(3, 3) = 6R(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 VVV vertices, EEE edges and FFF faces,

V−E+F=2.\displaystyle V - E + F = 2.V−E+F=2.

Why. For a tree, E=V−1E = V - 1E=V−1 and F=1F = 1F=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 EEE and FFF both drop by 111 and V−E+FV - E + FV−E+F stays the same. Repeat until a tree is left.

A cube has V=8V = 8V=8, E=12E = 12E=12 and F=6F = 6F=6, and indeed 8−12+6=28 - 12 + 6 = 28−12+6=2.

How many edges a planar graph can have

In a simple planar graph with V≥3V \ge 3V≥3, every face has at least 333 edges on its border, and every edge borders at most 222 faces. So 3F≤2E3F \le 2E3F≤2E. Put this into Euler's formula:

E≤3V−6.\displaystyle E \le 3V - 6.E≤3V−6.

If the graph has no triangle, every face has at least 444 edges, so 4F≤2E4F \le 2E4F≤2E and E≤2V−4E \le 2V - 4E≤2V−4.

Two graphs that are not planar.

  • K5K_5K5​ has V=5V = 5V=5 and E=10E = 10E=10, but 3V−6=93V - 6 = 93V−6=9.
  • K3,3K_{3,3}K3,3​ has no triangle, V=6V = 6V=6 and E=9E = 9E=9, but 2V−4=82V - 4 = 82V−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 K5K_5K5​ or K3,3K_{3,3}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)\chi(G)χ(G), read "chi of GGG".

  • χ(Kn)=n\chi(K_n) = nχ(Kn​)=n, because every two vertices are joined.
  • χ(G)≤2\chi(G) \le 2χ(G)≤2 exactly when GGG is bipartite.
  • An odd cycle needs 333 colours.
  • Greedy bound. Colour the vertices one at a time with the first free colour. A vertex has at most Δ\DeltaΔ neighbours, so χ(G)≤Δ+1\chi(G) \le \Delta + 1χ(G)≤Δ+1, where Δ\DeltaΔ is the largest degree.

For planar graphs, E≤3V−6E \le 3V - 6E≤3V−6 gives an average degree below 666, so some vertex has degree at most 555. Remove it, colour the rest by induction, and put it back with one of 666 colours: every planar graph can be coloured with 666 colours. The four colour theorem (Appel and Haken, 1976, with a computer check) says that 444 colours always suffice.

Ramsey numbers

Among any 666 people, there are always 333 who all know each other or 333 who are all strangers to each other.

Proof. Draw K6K_6K6​ and colour an edge red for "know each other" and blue for "strangers". Pick a person PPP. Of the 555 edges at PPP, at least 333 have the same colour by the pigeonhole principle, say red, to AAA, BBB and CCC.

  1. If any edge among AAA, BBB, CCC is red, it forms a red triangle with PPP.
  2. If none is red, then AAA, BBB, CCC form a blue triangle.

Five people are not enough. Colour the 555 sides of a pentagon red and its 555 diagonals blue. The red edges form a 555-cycle and the blue edges form another 555-cycle, a star shape, and neither has a triangle.

The Ramsey number R(3,3)R(3, 3)R(3,3) is the smallest nnn such that every red and blue colouring of KnK_nKn​ has a one-colour triangle. We have shown R(3,3)=6R(3, 3) = 6R(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 K17K_{17}K17​ has 161616 edges, so at least 666 share a colour. Among those 666 neighbours, an edge of that colour makes a triangle, and otherwise two colours are left on K6K_6K6​. So R(3,3,3)≤17R(3, 3, 3) \le 17R(3,3,3)≤17, and in fact R(3,3,3)=17R(3, 3, 3) = 17R(3,3,3)=17. Larger Ramsey numbers are very hard: R(4,4)=18R(4, 4) = 18R(4,4)=18, but R(5,5)R(5, 5)R(5,5) is still unknown.

Practise with new numbers

Try it in Python

The program checks every red and blue colouring of K5K_5K5​ and of K6K_6K6​, and counts the colourings with no one-colour triangle.

Read it first. Then run it. How many colourings of K5K_5K5​ avoid a one-colour triangle?

1. Change the program to print one colouring of K5K_5K5​ that works. Is its red part a 555-cycle?

2. Why is the count for K6K_6K6​ zero? Use the proof above to explain it.

Common mistakes

  • Forgetting the outside face. It counts in FFF.
  • Using E≤3V−6E \le 3V - 6E≤3V−6 for a graph with no triangle. Then the sharper E≤2V−4E \le 2V - 4E≤2V−4 holds.
  • A bound is not a proof of planarity. E≤3V−6E \le 3V - 6E≤3V−6 can hold for a graph that is still not planar.
  • The greedy bound is not exact. A star has Δ\DeltaΔ large but χ=2\chi = 2χ=2.

Remember these

  • Connected planar drawing: V−E+F=2V - E + F = 2V−E+F=2.
  • Simple planar, V≥3V \ge 3V≥3: E≤3V−6E \le 3V - 6E≤3V−6; no triangle: E≤2V−4E \le 2V - 4E≤2V−4. K5K_5K5​ and K3,3K_{3,3}K3,3​ are not planar.
  • χ(Kn)=n\chi(K_n) = nχ(Kn​)=n; bipartite means χ≤2\chi \le 2χ≤2; odd cycle needs 333; χ≤Δ+1\chi \le \Delta + 1χ≤Δ+1.
  • R(3,3)=6R(3, 3) = 6R(3,3)=6 and R(3,3,3)=17R(3, 3, 3) = 17R(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.

  1. A connected planar graph has 888 vertices and 131313 edges. How many faces does its drawing have?
  1. Can a simple planar graph have 777 vertices and 161616 edges?
  1. What is the chromatic number of the cycle C9C_9C9​?
  1. A graph has largest degree 444. What does the greedy bound say about its chromatic number?
  1. Why does the proof of R(3,3)≤6R(3, 3) \le 6R(3,3)≤6 fail for 555 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.
No payment. You can leave at any time.

Problems (3)

A connected planar graph with 10 vertices is drawn without crossings, and every face of the…Hard · High School (11–12) · by StemPy Lab
Three houses each need a path to each of three wells, nine paths in all, drawn on flat ground…Advanced · High School (11–12) · by StemPy Lab
The 15 edges of K₆ are coloured red or blue…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Graph Theory
← Trees, bipartite graphs and Euler trailsNext →

Discussion (0)

Log in to join the discussion.

Loading…

; so
K5K_5K5​
and
K3,3K_{3,3}K3,3​
are not planar. A colouring gives joined vertices different colours. Ramsey's theorem says that complete disorder is impossible: any
666
people include
333
mutual friends or
333
mutual strangers, so
R(3,3)=6R(3, 3) = 6R(3,3)=6
.

Question Sets (1)

Graph Theory: Test Yourself10 questions · by StemPy Lab

Notes (1)

Graph Theory: Quick RevisionNote · by StemPy Lab