In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.)
A matching that covers 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.
Read more about Factor-critical Graph: Examples, Characterizations, Properties, Applications, Generalizations and Related Concepts
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)