In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) 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.
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) 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.
Source: Wikipedia "Factor-critical graph" · CC BY-SA 4.0
Share this article: X · Bluesky