Matpic
mathematics, in pictures
Concept

Graph minor

A graph obtained from another by deleting vertices and edges and contracting edges into points. Many properties survive taking minors, and each such property is decided by a finite list of forbidden minors.

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

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 The seven graphs of the Petersen family. Seven small graph drawings, K₆, G7, K₃,₃,₁, K₄,₄ minus an edge, G8, G9, Petersen graph, arranged by vertex count with 6 arrows for the triangle-to-star exchanges between them.

Seven graphs that must link

Six points joined in every way cannot be placed in space without two disjoint triangles hooking together. Trade any triangle for a three-pointed star, or a star back for a triangle, and the property survives; doing it in every possible way from K₆ reaches exactly seven graphs, the Petersen graph among them, and stops. Every placement of every one of them links, by the same parity count. Remove any edge from any of them, and placements that link nothing appear at once. The seven are the whole answer: a graph must link exactly when it contains one of them.

topology · Linking number

Named alongside it

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

Complete graphDelta y exchangeEuler formulaExhaustive searchGraph colouringIntrinsically linkedLinking numberParityPetersen graphPlanar graphPlanaritySubdivision

All concepts