Matching Augmenting Path

Last updated Nov 1, 2022

Suppose $G$ is an Undirected Graph and $M \subset E(G)$ is a Matching on $G$. Suppose $P$ is an $M$-Alternating Path on $G$ of length $n \in \mathbb{N}$ from $u \in V(G)$ to $v \in V(G)$. Then $P$ is an $M$-augmenting path if $u$ and $v$ are both $M$-exposed.

1. Augmenting Network Flow Paths for Bipartite Matching Flow Formulation are Matching Augmenting Paths
2. If $P = (e_{1}, \dots, e_{n})$ is an $M$-augmenting path, then $e_{1}, e_{n} \not\in M$. If $e_{1}$ was, then $u$ would be covered by $M$. If $e_{n}$ was, then $v$ would be covered by $M$. Thus $n$ is odd and only $e_{2i} \in M$ for $i \in [\frac{n-1}{2}]$.

• Natural Numbers
• Graph Edge
• Graph Vertex