# Matchings in graphs

## Matchings

1. Let $G=(V,E)$ be an undirected graph. Without loss of generality, $G$ is connected. A matching in $G$ is a set $M\subseteq E$ of edges such that no two edges in $M$ are incident.
2. An edge in $M$ is called matched, an edge in $E\setminus M$ is unmatched.
3. A node $v\in V$ is matched with respect to a matching $M$ if it is incident to a matched edge; otherwise, $v$ is called free or exposed.
4. A matching is called perfect if there is no exposed node.

Remark: A perfect matching $M$ is only possible if $|V|$ is even. Then $M$ is perfect if, and only if, $|M|=|V|/2$.

## Alternating and augmenting paths

1. A path $p$ in an undirected graph $G=(V,E)$ is called alternating with respect to some matching $M$ if, for any two successive edges on $p$, exactly one of them belongs to $M$. In other words, the edges in $M$ and the edges not in $M$ appear strictly alternatingly on $p$.
2. An alternating path $p$ in an undirected graph $G=(V,E)$ is called augmenting with respect to some matching $M$ if both of its end nodes are exposed.
3. Augmenting a matching $M$ along an augmenting path $p$ means increasing the size of $M$ by one as follows:
1. Each edge of $p$ that was in $M$ immediately before this augmentation step, is removed from $M$.
2. Each edge of $p$ that was not in $M$ immediately before this augmentation step, is inserted in $M$.

## Finding augmenting paths

To find alternating paths in a matching $M$, a graph traversal strategy is chosen and modified as follows:

1. Whenever the current node $v$ has been reached via an edge in $M$, only incident edges in $E\setminus M$ are considered for seeing new nodes.
2. Mirror-symmetrically, whenever the current node $v$ has been reached via an edge in $E\setminus M$, only the (unique) incident edge in $M$, if existing, is considered for seeing a new node.

To find augmenting paths, the start node must be an exposed node.

Remark on the implementation: This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph:

1. Duplicate each matched node $v$ giving $v_1$ and $v_2$.
2. Replace each edge $\{v,w\}$ by two arcs, $(v,w)$ and $(w,v)$.
3. For each matched node $v$:
1. Let all incoming arcs of $v$ in $M$ point to $v_1$ and all outgoing arcs in $E\setminus M$ leave $v_1$.
2. Mirror-symmetrically, let all incoming arcs of $v$ in $E\setminus M$ point to $v_2$ and all outgoing arcs of $v$ in $M$ leave $v_2$.

Caveat: If the graph is not bipartite, no graph traversal strategies, modified as described above, guarantees to find an augmenting path if there is one; blossom handling is necessary in addition.

## Blossoms

Definitions:

1. For a matching $M$ in $G$, a blossom is a cycle $B$ of odd length in $G$ such that $\lfloor|B|/2\rfloor$ edges on $B$ are matched and the remaining node on $B$ is matched as well (by an edge not on $B$, in fact).
2. The unique matched edge with exactly one incident node on $B$ is called the stem of the blossom.
3. Shrinking a blossom $B$ means:
1. Insert a new node $u_B$ in $V$.
2. For each edge $\{v,w\}$ such that $v$ is on $B$ and $w$ is not: Replace $\{v,w\}$ by a new edge $\{u_B,w\}$.
3. Remove all nodes and edges on $B$.
4. An augmenting path $p$ conforms to $B$ if $p$ contains the stem.

Statement: Let $G=(V,E)$ be an undirected graph, $M$ a matching in $G$, and $B$ a blossom. Further, let $G'=(V',E')$ be the undirected graph resulting from shrinking $B$, and let $M'$ be the restriction of $M$ to $G'$. There is an augmenting path conforming to $B$ in $G$ with respect to $M$ if, and only if, there is an augmenting path in $G'$ with respect to $M'$ that contains $u_B$.

Proof: First suppose there is a conforming augmenting path $p$ in $G$ with respect to $M$. According to either possible orientation of $p$, let $s$ and $t$ denote the first and the last node of $p$. Moreover, let $v$ and $w$ denote the first and the last node of $p$ that also belongs to $B$ (possibly $v=w$). The concatenation of the subpaths of $p$ from $s$ to $v$ and from $w$ to $t$ is an augmenting path in $G'$, and this path contains $u_B$.

So, consider the case that there is an augmenting path $p$ in $G'$ with respect to $M'$, and that $p$ contains $u_B$. Since $u_B$ is matched, $u_B$ is not an end node of $p$, so $p$ contains the stem of $B$ because this is the only matched edge incident to $u_B$. Let $v$ be the node of $B$ incident to the stem and let $w$ be the node on $p$ that is farthest away from $v$ on $p$ among all nodes of $p$ that also belong to $B$. Exactly one of the two subpaths of $B$ from $v$ to $w$ yields a conforming augmenting path by concatenation with the two subpaths of $p$ from the end nodes of $p$ up to $v$ and $w$, respectively.