9.1. Matching and independency.
Two edges in a graph are independent
if they are not adjacent in G. An independent set of edges in a graph G is a set of edges,
each two of which are independent (nonadjacent). The edge independence number is the Maximum cardinality among the
independent sets of edges of G. An independent
set of G is called matching in G. A matching of maximum cardinality is a maximum matching.
Statement
9.1. The
number of edges in a maximum matching of G is the edge independence
number of G.
If M is a matching in a graph G with the property that every vertex of G is incident with an edge of M, then M is a perfect matching in G.
Statement
9.2. If G
has a perfect matching M, then G has even order and is a 1-regular
spanning subgraph of G.
A vertex that is incident with an edge of M is called M-saturated, otherwise the vertex is M-unsaturated.
Theorem 9.3.: Let and
be matchings in
a graph G. Then each component of the spanning subgraph H of G
with
(the symmetric
difference) is one of the following types:
-
an isolated vertex
-
an even cycle whose edges are alternately in
and in
,
-
a nontrivial path whose edges are alternately in
and in
and
such that each end-vertex of the path s either an -unsaturated vertex or an
-unsaturated
vertex but not both.
Proof.
First we note that . Otherwise, H would contain a vertex with
. So v would incident with at least two
edges in the same matching.
Since , every components of H is a path (possibly
trivial) or a cycle.
Since no two edges in a matching adjacent, the edges in each cycle
and path in H are alternately in and
. Thus each cycle is even.
Suppose that is an edge of H
and u is the endvertex of a path P (which is a component of H ).
Since , it follows that either
.
If , then u is an
-saturated vertex. We will show that u
is
-unsaturated.
Suppose the opposite: u is -saturated vertex. This case there is an edge f
in
such
that f is incident to u. Therefore e and f are
adjacent,
. Thus,
. But this is impossible since u is the
end-vertex of P. So, u is an
-unsaturated vertex.
Similarly can we
prove that if then u
is an
-unsaturated vertex.
As an illustration see the following example.

Figure 9.1. An example to illustrate the statement of Theorrem 9.3.
Let M be a matching in a graph G. An M-alternating path of G is a path whose edges are alternately in M and not in M. An M-augmenting path is an M-alternating path both of whose end-vertices are M-unsaturated vertices.
Theorem 9.4. (Berge, 1957): A matching M in a graph G is a maximum matching iff there exists no M-augmenting path in G.
- Assume that M is a maximum matching in G and that there exists an M-augmenting path P in G. Necessarily, P has odd length.
Let
denote the edges of P belonging to M, and let
. Since
, the set
is a matching having cardinality exceeding that of M, producing a contradiction.
- Conversely, let
be a matching in a graph G, and suppose that there exists no
-augmenting path in G.
Let
be a maximum matching in G. By the first part of the proof there is no
-augmenting path in G.
Let H be the spanning subgraph of G with
.
Suppose that
is a component of H that is neither an isolated vertex nor an even cycle.
Then, it follows from the Theorem 8.1 that
is a path of even length whose edges are alternately in
and in
, for otherwise, there would exist a path in G that is either
-augmenting or
-augmenting, which is impossible. It follows from the Theorem 9.3 that
,
which implies that
.
So, is a maximum matching.