Editing Matching (graph theory) (section)

== Definitions ==

Given a [[Graph (discrete mathematics)|graph]] {{math|1=''G'' = (''V'',&thinsp;''E''),}} a '''matching''' ''M'' in ''G'' is a set of pairwise [[non-adjacent]] edges, none of which are [[loop (graph theory)|loop]]s; that is, no two edges share common vertices.

A vertex is '''matched''' (or '''saturated''') if it is an endpoint of one of the edges in the matching.  Otherwise the vertex is '''unmatched''' (or '''unsaturated''').

A '''maximal matching''' is a matching ''M'' of a graph ''G'' that is not a subset of any other matching. A matching ''M'' of a graph ''G'' is maximal if every edge in ''G'' has a non-empty intersection with at least one edge in ''M''. The following figure shows examples of maximal matchings (red) in three graphs.

:[[File:Maximal-matching.svg]]

A '''maximum matching''' (also known as maximum-cardinality matching<ref>Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>) is a matching that contains the largest possible number of edges.  There may be many maximum matchings.  The '''matching number''' <math>\nu(G)</math> of a graph {{mvar|G}} is the size of a maximum matching. Every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in the same three graphs.

:[[File:Maximum-matching-labels.svg]]

A '''[[perfect matching]]''' is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is [[incidence (geometry)|incident]] to an edge of the matching. A matching is perfect if <math>|M|=|V|/2</math>. Every perfect matching is maximum and hence maximal. In some literature, the term '''complete matching''' is used. In the above figure, only part (b) shows a perfect matching. A perfect matching is also a minimum-size [[edge cover]]. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover: {{tmath|\nu(G) \le \rho(G)}}. A graph can only contain a perfect matching when the graph has an even number of vertices.

A '''near-perfect matching''' is one in which exactly one vertex is unmatched.  Clearly, a graph can only contain a near-perfect matching when the graph has an [[odd number]] of vertices, and near-perfect matchings are maximum matchings. In the above figure, part (c) shows a near-perfect matching. If every vertex is unmatched by some near-perfect matching, then the graph is called [[factor-critical graph|factor-critical]].

Given a matching ''M'', an '''alternating path''' is a path that begins with an unmatched vertex<ref>{{Cite web|url=http://diestel-graph-theory.com/basic.html|title=Preview}}</ref> and whose edges belong alternately to the matching and not to the matching. An '''augmenting path''' is an alternating path that starts from and ends on free (unmatched) vertices. [[Berge's lemma]] states that a matching ''M'' is maximum if and only if there is no augmenting path with respect to ''M''.

An '''[[induced matching]]''' is a matching that is the edge set of an [[induced subgraph]].<ref>{{citation
 | last = Cameron | first = Kathie
 | department = Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987
 | doi = 10.1016/0166-218X(92)90275-F
 | issue = 1–3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 1011265
 | pages = 97–102
 | title = Induced matchings
 | volume = 24
 | year = 1989| doi-access = free
 }}</ref>