Graphs · step 10 of 14

Planarity & Euler’s formula

For any connected planar graph drawn without crossings, V − E + F = 2, where F counts faces including the unbounded one. The formula yields hard edge bounds: E ≤ 3V − 6 for simple planar graphs with V ≥ 3, and E ≤ 2V − 4 when the graph is also triangle-free. Violating a bound proves non-planarity in two lines.

Practise planarity & euler’s formula free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Count V, E and F on a drawingDo not forget the outer face — it is one of the F.
Derive the edge boundEach face is bounded by at least 3 edges and each edge borders at most 2 faces, so 2E ≥ 3F. Substituting into Euler gives E ≤ 3V − 6.
Use the triangle-free boundIf there is no triangle, every face has at least 4 edges, giving 2E ≥ 4F and E ≤ 2V − 4.
Fall back on KuratowskiIf the counting bounds pass, look for a K₅ or K_{3,3} subdivision — that characterises non-planarity exactly.

Worked example

Prove K₅ and K_{3,3} are not planar.

K₅: V = 5 and E = C(5,2) = 10. The bound gives 3V − 6 = 9.
10 > 9, so K₅ is not planar.
K_{3,3}: V = 6, E = 9. The general bound 3V − 6 = 12 is satisfied, so it does not settle it.
But K_{3,3} is bipartite hence triangle-free, so E ≤ 2V − 4 = 8. Since 9 > 8, it is not planar.

Answer. Neither is planar — K₅ fails E ≤ 3V − 6, and K_{3,3} fails the triangle-free bound E ≤ 2V − 4.

Where marks get dropped

These are the specific errors that cost credit on planarity & euler’s formula questions — QED's rubric penalises each of them separately.

Omitting the unbounded face when counting F. Euler’s formula fails immediately without it.
Applying E ≤ 3V − 6 to disconnected graphs without care — Euler’s formula in the form V − E + F = 2 assumes connectivity (otherwise it is 1 + c).
Using the general bound on K_{3,3} and concluding it is planar. The bound is necessary, not sufficient.

Practise this until it is automatic

Unlimited fresh questions

QED generates new planarity & euler’s formula problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Planarity & Euler’s formula — frequently asked questions

What is Kuratowski’s theorem?

A graph is planar if and only if it contains no subdivision of K₅ or K_{3,3}. Wagner’s version states the same with minors instead of subdivisions.

How does Euler’s formula change for disconnected graphs?

V − E + F = 1 + c where c is the number of components. The connected case c = 1 gives the familiar 2.

What is the four colour theorem?

Every planar graph is 4-colourable. It follows from planarity’s sparsity but the full proof requires computer-assisted case checking.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make planarity & euler’s formula exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →