graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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 discret ...

with an

odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...

of vertices in which deleting one vertex in every possible way results in a graph with 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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...

, 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 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 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 (graph theory), 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 d ...

. This is a partition of the graph's 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 * Desir ...

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. *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 theoretical 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 ...

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

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 i ...

with an odd number of vertices. More generally, whenever a graph has an odd number of vertices and contains a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, 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 is factor-critical, then so is the Mycielskian 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 (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

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. Examples include the 5-vertex graph of a

square pyramid In geometry, a square pyramid is a Pyramid (geometry), pyramid with a square base and four triangles, having a total of five faces. If the Apex (geometry), apex of the pyramid is directly above the center of the square, it is a ''right square p ...

and the 11-vertex graph of the

gyroelongated pentagonal pyramid In geometry, the gyroelongated pentagonal pyramid is a polyhedron constructed by attaching a pentagonal antiprism to the base of a pentagonal pyramid. An alternative name is diminished icosahedron because it can be constructed by removing a pe ...

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 railway) without blocking the path underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somet ...

). 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 A contract is an agreement that specifies certain legally enforceable rights and obligations pertaining to two or more parties. A contract typically involves consent to transfer of goods, services, money, or promise to transfer any of those a ...

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 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 Axiomatic system, axiomatically, the most significant being in terms ...

, 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 theoretical 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 p ...

Applications

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

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s for maximum matching 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 co ...

, 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 proper 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 ...

(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 methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

. 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 maximum matching; 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 ...

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)