all vertices other than . Then is factor-critical if and only if there is a set of paths in , alternating between matched and unmatched edges, that connect to each of the other vertices in . Based on this property, it is possible to determine in linear time whether a graph with a given near-perfect matching is factor-critical.

Examples

Any odd-length cycle graph is factor-critical, as is any complete graph with

1.Previous
3.Next