factor-critical graph
{{Short description|Graph of n vertices with a perfect matching for every subgraph of n-1 vertices}}
{{Use mdy dates|cs1-dates=ly|date=February 2025}}
{{CS1 config|mode=cs2}}
File:Factor critical.svgs of the subgraphs formed by removing one of its vertices.]]
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph{{citation
| last1 = Cornuéjols | first1 = G. | author1-link = Gérard Cornuéjols
| last2 = Pulleyblank | first2 = W. R. | author2-link = William R. Pulleyblank
| doi = 10.1007/BF02579340
| issue = 1
| journal = Combinatorica
| mr = 716420
| pages = 35–52
| title = Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
| volume = 3
| year = 1983| s2cid = 35825797 }}.) 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.
Definition and 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 {{mvar|v}} of the graph, there exists a maximum matching that does not include {{mvar|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.{{citation
| last = Gallai | first = T. | authorlink = Tibor Gallai
| journal = Magyar Tud. Akad. Mat. Kutató Int. Közl.
| mr = 0166777
| pages = 135–139
| title = Neuer Beweis eines Tutte'schen Satzes
| volume = 8
| year = 1963}}. As cited by {{citation
| last1 = Frank | first1 = András | author1-link = András Frank
| last2 = Szegő | first2 = László
| doi = 10.1002/jgt.10055
| issue = 2
| journal = Journal of Graph Theory
| mr = 1926313
| pages = 110–119
| title = Note on the path-matching formula
| url = http://www.cs.elte.hu/~frank/cikkek/FrankJ43.PDF
| volume = 41
| year = 2002| citeseerx = 10.1.1.20.7918 | s2cid = 206076722 }}.
- László Lovász proved that a graph is factor-critical if and only if it has an odd ear decomposition. This is a partition of the graph's 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 already given, the ear decomposition can be chosen in such a way that each ear alternates between matched and unmatched edges.
{{citation|first=L.|last=Lovász|authorlink=László Lovász|title=A note on factor-critical graphs|journal=Studia Sci. Math. Hungar.|volume=7|year=1972|pages=279–280|mr=0335371}}.{{citation|title=Combinatorial Optimization: Theory and Algorithms|volume=21|series=Algorithms and Combinatorics|first1=Bernhard H.|last1=Korte|author1-link = Bernhard Korte|first2=Jens|last2=Vygen|edition=4th|publisher=Springer-Verlag|year=2008|isbn=978-3-540-71843-7|contribution=10.4 Ear-Decompositions of Factor-Critical Graphs|url=https://books.google.com/books?id=UnYwgPltSjwC&pg=PA235|pages=235–241}}.
- A graph is also factor-critical if and only if it can be reduced to a single vertex 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.{{citation
| last1 = Pulleyblank | first1 = W. R. | author1-link = William R. Pulleyblank
| last2 = Edmonds | first2 = J. | author2-link = Jack Edmonds
| editor1-last = Berge | editor1-first = C. | editor1-link = Claude Berge
| editor2-last = Ray-Chaudhuri | editor2-first = D. K. | editor2-link = Dwijendra Kumar Ray-Chaudhuri
| contribution = Facets of 1-matching polyhedra
| doi = 10.1007/BFb0066196
| pages = 214–242
| publisher = Springer-Verlag
| series = Lecture Notes in Mathematics
| title = Hypergraph Seminar
| volume = 411
| year = 1974
| isbn = 978-3-540-06846-4}}. 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 {{mvar|G}} is given together with a choice of a vertex {{mvar|v}} and a matching {{mvar|M}} that covers all vertices other than {{mvar|v}}. Then {{mvar|G}} is factor-critical if and only if there is a set of paths in {{mvar|G}}, alternating between matched and unmatched edges, that connect {{mvar|v}} to each of the other vertices in {{mvar|G}}. Based on this property, it is possible to determine in linear time whether a graph {{mvar|G}} with a given near-perfect matching is factor-critical.{{citation
| last1 = Lou | first1 = Dingjun
| last2 = Rao | first2 = Dongning
| journal = The Australasian Journal of Combinatorics
| mr = 2080453
| pages = 51–56
| title = Characterizing factor critical graphs and an algorithm
| url = http://ajc.maths.uq.edu.au/pdf/30/ajc_v30_p051.pdf
| volume = 30
| year = 2004}}.
Examples
File:Friendship graphs.svgs, examples of non-Hamiltonian factor-critical graphs]]
File:Gyroelongated pentagonal pyramid.png, a claw-free factor-critical graph]]
Any odd-length cycle graph is factor-critical, as is any complete graph with an odd number of vertices. More generally, whenever a graph has an odd number of vertices and contains a Hamiltonian cycle, it is factor-critical. In such a graph, the near-perfect matchings can be obtained by removing one vertex from the cycle and choosing matched edges in alternation along the remaining path. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but do not have Hamiltonian cycles.
If a graph {{mvar|G}} is factor-critical, then so is the Mycielskian of {{mvar|G}}. For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.{{citation
| last = Došlić | first = Tomislav
| issue = 3
| journal = Discussiones Mathematicae Graph Theory
| mr = 2232992
| pages = 261–266
| title = Mycielskians and matchings
| url = http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=pdf&nIdA=14414&nIdSesji=-1
| volume = 25
| year = 2005
| doi=10.7151/dmgt.1279| doi-access = free
}}.
Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical, because removing any vertex will leave a connected claw-free graph with an even number of vertices, and these always have a perfect matching.{{citation
| last1 = Favaron | first1 = Odile | author1-link = Odile Favaron
| last2 = Flandrin | first2 = Evelyne
| last3 = Ryjáček | first3 = Zdeněk
| issue = 2
| journal = Discussiones Mathematicae Graph Theory
| mr = 1627955
| pages = 271–278
| title = Factor-criticality and matching extension in DCT-graphs
| url = http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=pdf&nIdA=3481&nIdSesji=-1
| volume = 17
| year = 1997 | doi=10.7151/dmgt.1054| citeseerx = 10.1.1.25.6314
}}.
Examples include the 5-vertex graph of a square pyramid and the 11-vertex graph of the gyroelongated pentagonal pyramid.
Properties
Factor-critical graphs must always have an odd number of vertices, and must be 2-edge-connected (that is, they cannot have any bridges).{{citation
| last = Seyffarth | first = Karen
| doi = 10.1016/0012-365X(93)90334-P
| issue = 1–3
| journal = Discrete Mathematics
| mr = 1226141
| pages = 183–195
| title = Packings and perfect path double covers of maximal planar graphs
| volume = 117
| year = 1993| doi-access = free
}}. However, they are not necessarily 2-vertex-connected; the friendship graphs provide a counterexample. It is not possible for a factor-critical graph to be bipartite, because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition.
Every 2-vertex-connected factor-critical graph with {{mvar|m}} edges has at least {{mvar|m}} different near-perfect matchings, and more generally every factor-critical graph with {{mvar|m}} edges and {{mvar|c}} blocks (2-vertex-connected components) has at least {{math|m − c + 1}} different near-perfect matchings. The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.{{citation
| last1 = Liu | first1 = Yan
| last2 = Hao | first2 = Jianxiu
| doi = 10.1016/S0012-365X(01)00204-7
| issue = 1–3
| journal = Discrete Mathematics
| mr = 1874747
| pages = 259–266
| title = The enumeration of near-perfect matchings of factor-critical graphs
| volume = 243
| year = 2002| doi-access =
}}.
Any connected graph may be transformed into a factor-critical graph by contracting sufficiently many of its edges. The minimal sets of edges that need to be contracted to make a given graph {{mvar|G}} factor-critical form the bases of a matroid, a fact that implies that a greedy algorithm may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in polynomial time.{{citation
| last = Szigeti | first = Zoltán
| doi = 10.1007/BF01844849
| issue = 2
| journal = Combinatorica
| mr = 1401896
| pages = 233–241
| title = On a matroid defined by ear-decompositions of graphs
| volume = 16
| year = 1996| s2cid = 206806006
}}. For an earlier algorithm for contracting the minimum number of (unweighted) edges to reach a factor-critical graph, see {{citation
| last = Frank | first = András | author-link = András Frank
| doi = 10.1007/BF01202790
| issue = 1
| journal = Combinatorica
| mr = 1221177
| pages = 65–81
| title = Conservative weightings and ear-decompositions of graphs
| volume = 13
| year = 1993| s2cid = 10857300 }}.
Applications
A blossom is a factor-critical subgraph of a larger graph. Blossoms play a key role in Jack Edmonds' algorithms for maximum matching and minimum weight perfect matching in non-bipartite graphs.{{citation | author=Edmonds, Jack | authorlink = Jack Edmonds | title=Paths, Trees and Flowers | journal=Canadian Journal of Mathematics | volume=17 | year=1965 | pages=449–467 | mr = 0177907 | doi=10.4153/CJM-1965-045-4| s2cid = 18909734 | doi-access=free }}.
In polyhedral combinatorics, factor-critical graphs play an important role in describing facets of the matching polytope of a given graph.