Factor-critical Graph - Characterizations

Characterizations

Factor-critical graphs may be characterized in several different ways, other than their definition as graphs in which each vertex deletion allows for a perfect matching:

• Tibor Gallai proved that a graph is factor-critical if and only if it is connected and, for each node v of the graph, there exists a maximum matching that does not include v. It follows from these properties that the graph must have an odd number of vertices and that every maximum matching must match all but one vertex.
• László Lovász proved that a graph is factor-critical if and only if it has an odd ear decomposition, a partition of its edges into a sequence of subgraphs, each of which is an odd-length path or cycle, with the first in the sequence being a cycle, each path in the sequence having both endpoints but no interior points on vertices in previous subgraphs, and each cycle other than the first in the sequence having exactly one vertex in previous subgraphs. For instance, the graph in the illustration may be partitioned in this way into a cycle of five edges and a path of three edges. In the case that a near-perfect matching of the factor-critical graph is also given, the ear decomposition can be chosen in such a way that each ear alternates between matched and unmatched edges.
• A graph is also factor-critical if and only if it can be reduced to a single graph by a sequence of contractions of odd-length cycles. Moreover, in this characterization, it is possible to choose each cycle in the sequence so that it contains the vertex formed by the contraction of the previous cycle. For instance, if one contracts the ears of an ear decomposition, in the order given by the decomposition, then at the time each ear is contracted it forms an odd cycle, so the ear decomposition characterization may be used to find a sequence of odd cycles to contract. Conversely from a sequence of odd cycle contractions, each containing the vertex formed from the previous contraction, one may form an ear decomposition in which the ears are the sets of edges contracted in each step.
• Suppose that a graph G is given together with a choice of a vertex v and a matching M that covers all vertices other than v. Then G is factor-critical if and only if there is a set of paths in G, alternating between matched and unmatched edges, that connect v to each of the other vertices in G. Based on this property, it is possible to determine in linear time whether a graph G with a given near-perfect matching is factor-critical.