Difficulty: Intermediate | Prerequisites: Basic graph terminology (vertices, edges, degree, subgraphs)
Graph theory sits at the intersection of discrete mathematics and computer science, and planarity is one of its central questions: can a given graph be drawn flat, with no edges crossing? This matters for circuit board design, network layout, and map colouring. You should already be comfortable with what a graph is, what vertices and edges are, and what it means for a graph to be connected. If those terms are unfamiliar, review your introductory graph theory notes first.
A planar graph can be drawn in the plane with no edge crossings. Euler's formula (V - E + F = 2) relates vertices, edges, and faces in any connected planar graph. Kuratowski's theorem gives a definitive test for non-planarity: a graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3.
Planar graph
A graph that can be drawn in the plane so that no two edges cross each other. In simple terms, think of it as a network you can sketch on a flat sheet of paper without any wires overlapping.
Plane graph (planar embedding)
A specific drawing of a planar graph in the plane with no crossings. In simple terms, this is one particular "flattened" layout of the graph, not just the abstract promise that such a layout exists.
Face
A connected region of the plane bounded by edges in a plane graph, including the unbounded outer region (the exterior face). Think of it as the enclosed "rooms" created by the edges, plus the infinite space surrounding the whole drawing.
Euler's formula
For any connected planar graph: V - E + F = 2, where V is the number of vertices, E the number of edges, and F the number of faces. In simple terms, this is a bookkeeping identity that always holds for connected planar graphs, no matter how they look.
Homeomorphic
Two graphs are homeomorphic if one can be obtained from the other by inserting or removing degree-2 vertices along edges. Think of it as stretching or compressing edges by adding or removing intermediate points, without changing the fundamental shape of the graph.
K5 (complete graph on 5 vertices)
The graph in which every one of the 5 vertices is connected to every other vertex, giving 10 edges total. In simple terms, it is the most connected graph you can build with 5 nodes.
K3,3 (complete bipartite graph)
A bipartite graph with two groups of 3 vertices each, where every vertex in one group is connected to every vertex in the other, giving 9 edges. Think of it as the "three houses, three utilities" problem: three houses each need a connection to gas, water, and electricity, and you cannot do it without crossings.
Kuratowski's theorem
A graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3. In simple terms, these two graphs are the "smallest" obstructions to planarity, and every non-planar graph contains a stretched version of at least one of them.
The formula V - E + F = 2 applies to any connected planar graph
V = number of vertices, E = number of edges, F = number of faces (including the exterior face)
You can use it as a planarity check: draw the graph, count V, E, and F, and verify the equation holds
If V - E + F does not equal 2, either the drawing has a crossing you missed or the graph is not planar
A useful corollary: for a simple connected planar graph with V ≥ 3, the inequality E ≤ 3V - 6 must hold
This gives a quick way to rule out planarity without drawing anything: if E > 3V - 6, the graph cannot be planar
Kuratowski's theorem is an "if and only if" result, meaning it is both necessary and sufficient
To show a graph is non-planar, find a subgraph homeomorphic to K5 or K3,3
"Homeomorphic to" means you are allowed to ignore degree-2 vertices that just subdivide an edge
K5 has 5 vertices and 10 edges; K3,3 has 6 vertices and 9 edges
In practice, the theorem is most useful for proving non-planarity. For proving planarity, it is usually easier to exhibit a planar embedding directly
Euler's formula: V - E + F = 2
Edge bound for simple connected planar graphs (V ≥ 3): E ≤ 3V - 6
Edge bound for simple connected bipartite planar graphs (V ≥ 3): E ≤ 2V - 4
Circuit board design relies on planarity: a single-layer printed circuit board can only be manufactured if the underlying connection graph is planar, since traces on one layer cannot cross. Map colouring, network visualisation, and VLSI chip layout all draw directly on these results.
Students often assume that if a particular drawing of a graph has crossings, the graph must be non-planar. It does not follow. The graph is non-planar only if no possible drawing avoids crossings.
Students sometimes forget to count the exterior (unbounded) face when applying Euler's formula. The exterior region counts as a face.
Kuratowski's theorem requires a homeomorphic copy of K5 or K3,3, not an exact copy. Students who look only for a literal K5 or K3,3 as a subgraph will miss subdivided versions and draw incorrect conclusions.
The inequality E ≤ 3V - 6 is necessary but not sufficient for planarity. A graph can satisfy this inequality and still be non-planar.
⚠️ You will almost certainly be asked to verify Euler's formula on a given graph. Count vertices, edges, and faces carefully, and remember the exterior face.
⚠️ Expect a question asking you to prove a specific graph is non-planar by identifying a K5 or K3,3 subdivision.
⚠️ The edge-bound corollary (E ≤ 3V - 6) is a common quick-check question: "show that K5 is non-planar" can be done in one line with this inequality.
True or false: A graph with 6 vertices and 13 edges can be planar.
Fill in the blank: Euler's formula states V - E + F = ___.
True or false: K3,3 has 9 edges.
True or false: If a drawing of a graph has edge crossings, the graph is definitely non-planar.
Fill in the blank: The two forbidden subgraphs in Kuratowski's theorem are ___ and ___.
Answers: 1. False (E ≤ 3V - 6 = 12). 2. 2. 3. True. 4. False (another drawing might avoid crossings). 5. K5 and K3,3.
Q: A connected planar graph has 8 vertices and 12 edges. How many faces does it have?
A: Using V - E + F = 2: 8 - 12 + F = 2, so F = 6.
Q: Prove that K5 is non-planar using the edge bound.
A: K5 has V = 5 and E = 10. The bound gives E ≤ 3(5) - 6 = 9. Since 10 > 9, K5 cannot be planar.
Q: What does Kuratowski's theorem say, and why is "homeomorphic" important in the statement?
A: The theorem states a graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3. "Homeomorphic" is important because the forbidden subgraph may have extra degree-2 vertices subdividing its edges; without this allowance, you would miss many non-planar graphs that contain a "stretched" version of K5 or K3,3 rather than an exact copy.
Q: A connected planar graph has 10 faces and 15 edges. How many vertices does it have?
A: V - 15 + 10 = 2, so V = 7.
This connects to graph colouring, because the Four Colour Theorem guarantees that every planar graph can be coloured with at most four colours. Planarity also links to topology (graphs on surfaces of higher genus) and to algorithm design, where efficient planarity-testing algorithms run in linear time.
planar graph, plane graph, Euler's formula for graphs, V - E + F = 2, Kuratowski's theorem, K5, K3,3, complete graph, complete bipartite graph, graph planarity, non-planar graph, edge crossing, face of a graph, exterior face, graph embedding, planar embedding, subdivision of a graph, homeomorphic graphs, circuit board design, four colour theorem, graph colouring, discrete mathematics, MATH 101