Factor-critical graph

A factor-critical graph, together with perfect matchings of the subgraphs formed by removing one of its vertices.

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. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.