Factor-critical graph

In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph^[1]^[2]) is a graph with an odd number of vertices in which deleting one vertex in every possible way results in a graph with a perfect matching, a way of grouping the remaining vertices into adjacent pairs.

A matching of all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.

^ Cite error: The named reference pe74 was invoked but never defined (see the help page).
^ Cornuéjols, G.; Pulleyblank, W. R. (1983), "Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem", Combinatorica, 3 (1): 35–52, doi:10.1007/BF02579340, MR 0716420, S2CID 35825797.

[pe74-1] Cite error: The named reference pe74 was invoked but never defined (see the help page).

[cp83-2] Cornuéjols, G.; Pulleyblank, W. R. (1983), "Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem", Combinatorica, 3 (1): 35–52, doi:10.1007/BF02579340, MR 0716420, S2CID 35825797.

[1]

[2]