Dominik Farhan

Definitions

We will assume $G = (V, E)$ to be an undirected graph.

Definition (Matching).

M \subseteq

is a matching if for different

\forall e,f \in M

e\cap f = \emptyset

Definition (maximum matching). Matching of

\max |M|

Definition (perfect matching). matchig is perfect if for each

v \in V \exists e \in M: e\cap v \neq \emptyset

Definition (M-covered vertex). Vertex is

M

-covered if there is an edge in

M

containing it.

Definition (M-exposed vertex). Vertex is M-exposed if it is not in any edge of the matching.

Definition (deficiency of G and M).

def(G)

is the minimum number of vertices exposed in any matching of

G

. Similarly

def(M)

is the number of vertices that are

M-exposed

for this particular matching.

Definition (Inessential vertex). Vertex is inessential if there is a maximum matching not containing it.

Definition (alternating path). Path is alternating (in a particular matching) if edges on it are alternately in or not and the first and the last vertex are both

M

-exposed.

Theorems

Theorem (Augmenting path and matching). Matching is maximum iff there is no augmenting path.

Proof.

\implies

By complementarity. Suppose there is an augmenting path. Then we can swap edges on that path, thus the matching cannot be maximum.

Proof ( $\Longleftarrow$ ).

Again by complementariy. Assume that $M$ is not maximum and there is $N$ with greater size. Let $F = M \Delta N$ . Observe that $G[F]$ contains only cycles and paths. Because edges have to alternate between matchings, all cycles are of even length. However we know that $|N| > |M|$ so there then must be a path of odd length which contains more edges from $N$ than from $M$ . This is an alternating path in $M$ .

Theorem (Little observation). For any

M

and all

A \subseteq V

it must hold that

def(M) \geq odd(G \setminus A) - |A|

Proof (Little observation).

Let's have the matching $M$ and some $A$ . When we remove $A$ from the graph we are left with some even and odd components. In the best possible scenario $M$ pairs all vertices in even components. We are left with the odd. In each odd components, in the best possible scenario, matching elements all but one vertex. This gives us $odd(G \setminus A)$ vertices we need to pair.

Again, in the best possible case all vertices in $A$ can be paired with the vertices in the odd components. We are left with $odd(G \setminus A) - |A|$ vertices. Which completes the proof.

Theorem (Week Tutte-Berge). For any

A\subseteq V

\max_{M} |M| = \min_{M} \frac{1}{2}(|V| - def(M)) \leq \min_{A \subseteq V} \frac{1}{2}(|V| - odd(G\setminus A) + |A|)

Theorem (Tutte-Berge). For any

A\subseteq V

\max_{M} |M| = \min_{A\subseteq V} \frac{1}{2}(|V| - odd(G\setminus A) + |A|)

There are two proofs of this theorem. One non-constructive which I will not attempt to carry out. However can be found here. The other is constructive and assumes reader to be fammiliar with Edmond's max matching algorithm. This proof is scatched without many import details bellow.

Proof (Tutte-Berge (bipartite case)).

Assume $G$ to be bipartite. Then we can apply Edmonds algorithm. No odd cycle can appear, so we can never get a blossom which we would need to contract. We are going to end up with matching that is maximal and some number of vertices that are deficient. So we are essentialy constructing the solution so that the equality always holds.

Proof (Tutte-Berge (general case)). Here, an edge between vertices with even distance from the root creates an odd cycle (blossom, denote it as

C

). Notice that there is an

M

-augmenting path in

G

iff there is an

M

-augmenting path in

G \times C

. So the idea is to contract any blossom and reduce it to previous case.

Theorem (Tutte).

G

has a perfect matching iff for all

A

subsets of vertices

odd(G \setminus A) \leq |A|.

This theorem is direct corollary of Tutte-Berge. However, in reality this special case was proven before Tutte-Berge. Again only rough description of the proof.

Proof ( $\implies$ ). Let's turn things around and assume that there is

A

such that

odd(G \setminus A) > |A|.

Then if there was a perfect matching it means that there is a matched edged between each odd component and some vertex in

A

which is clearly not possible.

Proof.

\Longleftarrow

This can be proved by rather complicated induction. Mayber I'll add this later.

Theorem (Gallai-Edmonds decomposition).

Tutte's theorem for matching

Definitions

Theorems