Matpic
mathematics, in pictures
Concept

Subdivision

A graph obtained from another by replacing edges with paths through new points of degree two. A graph contains a subdivision of K5 or K3,3 exactly when it cannot be drawn in the plane without crossings, which is Kuratowski's theorem.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none.

Two graphs that will not lie flat

Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

discrete · Planarity The Petersen graph, which a five-edge count rules off the plane. The Petersen graph drawn as an outer pentagon, an inner pentagram and five spokes: ten points, fifteen edges, girth five, and more edges than the 13.33 a flat drawing with five-edge faces allows.

Five spokes squeezed into K5

The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

discrete · Planarity

Named alongside it

The objects these essays reach for when they reach for this one.

Complete graphEuler formulaGraph colouringPlanar graphPlanarityCounting argumentCrossing numberExhaustive searchGraphGraph minorTopological invariant

All concepts