Graph minor

A graph obtained from another graph by deleting vertices or edges and contracting edges. The minor relation organizes graphs by structural containment and underlies major results in graph theory.

Edge contraction: An operation that merges the endpoints of an edge into one vertex, retaining their other incident edges. Contracting edges is the defining operation that creates graph minors.
Wagner's theorem: A theorem characterizing planar graphs as graphs with no minor isomorphic to K₅ or K₃,₃. It gives a concise forbidden-minor test for planarity.
Planar graph: A graph that can be drawn in the plane with no edges crossing except at shared endpoints. Planarity is characterized by excluding two specific graph minors.
Graph: A mathematical structure consisting of vertices joined by edges. Minors are formed by transforming graphs while retaining a graph as the result.
Subgraph: A graph formed by deleting vertices, edges, or both from another graph. Deleting vertices and edges produces subgraphs before any contractions are made.
Graph minor theorem: A theorem stating that finite graphs are well-quasi-ordered by the minor relation. It guarantees finite obstruction sets for minor-closed graph classes.
Treewidth: A measure of how closely a graph resembles a tree, defined through tree decompositions. Excluded-minor structure helps explain which graphs have bounded treewidth.
Path (graph theory): A sequence of distinct vertices joined consecutively by edges. Contractions shorten paths, while connected branch sets rely on paths.
Subdivision (graph theory): A graph formed by replacing edges with paths whose internal vertices are new. Subdivisions preserve paths, whereas contractions shorten them to obtain minors.
Robertson–Seymour theorem: The theorem that every minor-closed class of finite graphs has finitely many excluded minors. It turns minor containment into a finite characterization of graph families.

Linked from 9 pages