graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a mathematical discipline, a factor-critical graph (or hypomatchable graph.) is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

with vertices in which every subgraph of vertices has a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers 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.

Examples

Any odd-length

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

is factor-critical, as is any

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

with an odd number of vertices. More generally, every

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

graph with an odd number of vertices is factor-critical. The

friendship graph In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or -fan) is a planar, undirected graph with vertices and edges. The friendship graph can be constructed by joining copies of the cycle graph with a ...

s (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but not Hamiltonian. If a graph is factor-critical, then so is the

Mycielskian In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic ...

of . For instance, the

Grötzsch graph In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...

, the Mycielskian of a five-vertex cycle-graph, is factor-critical. Every 2-vertex-connected

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

with an odd number of vertices is factor-critical. For instance, the 11-vertex graph formed by removing a vertex from the

regular icosahedron In geometry, a regular icosahedron ( or ) is a convex polyhedron with 20 faces, 30 edges and 12 vertices. It is one of the five Platonic solids, and the one with the most faces. It has five equilateral triangular faces meeting at each vertex. It ...

(the graph of the

gyroelongated pentagonal pyramid In geometry, the gyroelongated pentagonal pyramid is one of the Johnson solids (). As its name suggests, it is formed by taking a pentagonal pyramid and "gyroelongating" it, which in this case involves joining a pentagonal antiprism to its base ...

) is both 2-connected and claw-free, so it is factor-critical. This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.

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 Tibor Gallai (born Tibor Grünwald, 15 July 1912 – 2 January 1992) was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes K� ...

proved that a graph is factor-critical if and only if it is

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

and, for each node of the graph, there exists a

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...

that does not include . 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 László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...

proved that a graph is factor-critical if and only if it has an odd

ear decomposition In graph theory, an ear of an undirected graph ''G'' is a path ''P'' where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of ''P'' has degree two in ''G''. A ...

, a partition of its edges into a sequence of subgraphs, each of which is an odd-length

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...

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 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.. 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 is given together with a choice of a vertex and a matching that covers 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

whether a graph with a given near-perfect matching is factor-critical.

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 A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...

). 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 edges has at least different near-perfect matchings, and more generally every factor-critical graph with edges and blocks (2-vertex-connected components) has at least different near-perfect matchings. The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.. 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 factor-critical form the bases of a

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

, a fact that implies that a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

Applications

A blossom is a factor-critical subgraph of a larger graph. Blossoms play a key role in

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s for

and minimum weight perfect matching in non-bipartite graphs. In

polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral comb ...

, factor-critical graphs play an important role in describing facets of the

matching polytope In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the the ...

of a given graph.

Generalizations and related concepts

A graph is said to be -factor-critical if every subset of vertices has a perfect matching. Under this definition, a hypomatchable graph is 1-factor-critical. Even more generally, a graph is -factor-critical if every subset of vertices has an -factor, that is, it is the vertex set of an -regular subgraph of the given graph. A

critical graph In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed ...

(without qualification) is usually assumed to mean a graph for which removing each of its vertices reduces the number of colors it needs in a

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

. The concept of criticality has been used much more generally in graph theory to refer to graphs for which removing each possible vertex changes or does not change some relevant property of the graph. A matching-critical graph is a graph for which the removal of any vertex does not change the size of a

; by Gallai's characterization, the matching-critical graphs are exactly the graphs in which every connected component is factor-critical. The

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...

of a critical graph is necessarily matching-critical, a fact that was used by Gallai to prove lower bounds on the number of vertices in a critical graph. Beyond graph theory, the concept of factor-criticality has been extended to

s by defining a type of ear decomposition on matroids and defining a matroid to be factor-critical if it has an ear decomposition in which all ears are odd..

References

{{reflist Graph families Matching (graph theory)