# Factorization

(Redirected from Perfect matching)

2010 Mathematics Subject Classification: Primary: 05C70 [MSN][ZBL]

in graph theory

The decomposition of a graph into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree $k$ is called a $k$-factor; a $1$-factor is also called a perfect matching. A graph is called $k$-factorizable (or $k$-factorable) if it can be represented as a union of edge-disjoint $k$-factors.

In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph with the same number of vertices in each part are $1$-factorizable. A connected graph is $2$-factorizable if and only if it is a regular graph of even degree. A graph $G$ has a $1$-factor if and only if it has an even number of vertices and if there is no subset of vertices $U$ such that the number of components with an odd number of vertices of the graph $G\setminus U$, obtained from $G$ by deleting the vertices of $U$, exceeds $|U|$. Every two-connected regular graph of degree 3 can be decomposed into a $1$-factor and a $2$-factor which are edge-disjoint.

Examples of non-regular factors are spanning trees (cf. Tree) and forests, spanning planar subgraphs (see Graph imbedding), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph $G$ is equal to

$$\max_k\left\lbrace\frac{g_k}{k-1}\right\rbrace,$$

where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.

How to Cite This Entry:
Perfect matching. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Perfect_matching&oldid=36120