Editing Perfect matching (section)

== Characterizations ==
[[Hall's marriage theorem]] provides a characterization of bipartite graphs which have a perfect matching.

The [[Tutte theorem]] provides a characterization for arbitrary graphs.

A perfect matching is a spanning [[Regular graph|1-regular]] subgraph, a.k.a. a [[1-factor]]. In general, a spanning ''k''-regular subgraph is a [[Factor (graph theory)|''k''-factor]].

A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows:  Let <math>G</math> be a [[Graph_(discrete_mathematics)|graph]] on even <math>n</math> vertices and <math>\lambda_1 > \lambda_2 > \ldots > \lambda_{\frac{n}{2}}>0</math> be <math>\frac{n}{2}</math> distinct nonzero [[imaginary number|purely imaginary numbers]]. Then <math>G</math> has a perfect matching if and only if there is a real [[skew-symmetric matrix]] <math>A</math> with graph <math>G</math> and  [[eigenvalues]] <math>\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_{\frac{n}{2}}</math>.<ref name=":1">Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004</ref> Note that the (simple) graph of a real symmetric or skew-symmetric matrix <math>A</math> of order <math>n</math> has <math>n</math> vertices and edges given by the nonzero off-diagonal entries of <math>A</math>.