Factor-critical graph

[3] More generally, every Hamiltonian graph with an odd number of vertices is factor-critical.

This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.

Every 2-vertex-connected factor-critical graph with m edges has at least m different near-perfect matchings, and more generally every factor-critical graph with m edges and c blocks (2-vertex-connected components) has at least m − c + 1 different near-perfect matchings.

The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.

The minimal sets of edges that need to be contracted to make a given graph G factor-critical form the bases of a matroid, a fact that implies that a greedy algorithm may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in polynomial time.

Blossoms play a key role in Jack Edmonds' algorithms for maximum matching and minimum weight perfect matching in non-bipartite graphs.