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.