Tutte's theorem on perfect matchings

A finite graph has a perfect matching exactly when deleting any vertex set leaves at most as many odd connected components as deleted vertices.

Perfect matching: A set of pairwise disjoint edges incident to every vertex of a graph. The theorem characterizes exactly when a graph has this spanning set of edges.
Graph theory: The mathematical study of vertices, edges, and the structures they form. Tutte's theorem is a structural result about finite graphs.
William Thomas Tutte: A British-Canadian mathematician who made foundational contributions to graph theory and combinatorics. He proved the criterion that now bears his name.
Maximum cardinality matching: A matching containing the largest possible number of edges in a graph. The theorem's deficiency count characterizes how far a graph is from a perfect matching.
Hall's marriage theorem: A bipartite graph has a matching covering one side exactly when every subset of that side has enough neighbors. Hall's neighborhood condition replaces odd-component counting in bipartite graphs.
Odd component: A connected component containing an odd number of vertices. After deletion, each odd component needs a distinct deleted vertex to pair its leftover vertex.
Matching (graph theory): A set of edges in a graph no two of which share a vertex. A perfect matching is a matching that covers every vertex.
Perfect factors and matchings in graphs: A research topic concerning spanning subgraphs whose components satisfy specified structural constraints. Tutte's work placed perfect matchings within a broader theory of graph factors.
Blossom algorithm: An algorithm for finding a maximum matching in a general graph by contracting odd alternating cycles. It handles odd-cycle structure that bipartite matching methods cannot directly resolve.
Petersen's theorem: Every bridgeless cubic graph has a perfect matching. It guarantees a perfect matching for a narrower graph class without testing every vertex set.

Linked from 5 pages