Editing Matching (graph theory) (section)

== Properties ==

In any graph without isolated vertices, the sum of the matching number and the [[edge covering number]] equals the number of vertices.<ref>{{citation|last=Gallai|first=Tibor|title=Über extreme Punkt- und Kantenmengen|journal=Ann. Univ. Sci. Budapest. Eötvös Sect. Math. |volume=2|pages=133–138|year=1959}}.</ref> If there is a perfect matching, then both the matching number and the edge cover number are {{math|{{!}}''V'' {{!}} / 2}}.

If {{math|''A''}} and {{math|''B''}} are two maximal matchings, then {{math|{{!}}''A''{{!}}&nbsp;≤&nbsp;2{{!}}''B''{{!}}}} and {{math|{{!}}''B''{{!}}&nbsp;≤&nbsp;2{{!}}''A''{{!}}}}. To see this, observe that each edge in {{math|''B''&nbsp;\&nbsp;''A''}} can be adjacent to at most two edges in {{math|''A''&nbsp;\&nbsp;''B''}} because {{math|''A''}} is a matching; moreover each edge in {{math|''A''&nbsp;\&nbsp;''B''}} is adjacent to an edge in {{math|''B''&nbsp;\&nbsp;''A''}} by maximality of {{math|''B''}}, hence

:<math>|A \setminus B| \le 2|B \setminus A |.</math>

Further we deduce that

:<math>|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.</math>

In particular, this shows that any maximal matching is a 2-approximation of a maximum matching and also a 2-approximation of a minimum maximal matching. This inequality is tight: for example, if {{math|''G''}} is a path with 3 edges and 4 vertices, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.

A spectral characterization of the matching number of a graph is given by Hassani Monfared and Mallik as follows:  Let <math>G</math> be a [[Graph_(discrete_mathematics)|graph]] on <math>n</math> vertices, and <math>\lambda_1 > \lambda_2 > \ldots > \lambda_k>0</math> be <math>k</math> distinct nonzero [[imaginary number|purely imaginary numbers]] where <math>2k \leq n</math>. Then the [[matching number]] of <math>G</math> is <math>k</math> if and only if (a) 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_k</math> and <math>n-2k</math> zeros, and (b) all real skew-symmetric matrices with graph <math>G</math> have at most <math>2k</math> nonzero [[eigenvalues]].<ref>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, https://arxiv.org/abs/1602.03590 </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 nonozero off-diagonal entries of <math>A</math>.