Matching Alternating Tree

Last updated Nov 1, 2022

Suppose $G$ is an Undirected Graph and $M$ is a Matching on $G$. Suppose $(T, r)$ is a Rooted Tree Subgraph of $G$. Then $(T, r)$ is an $M$-Matching Alternating Tree if

1. $r$ is exposed by $M$,
2. $\forall v \in T$, the Path from $v$ to $r$ on $T$ is an $M$-alternating path.

1. We have two special Sets $A(T)$ and $B(T)$ associated with an $M$-alternating tree defined as follows
   1. $A(T) = {v \in T : d(r, v) \text{ is odd}}$
   2. $B(T) = {v \in T : d(r, v) \text{ is even}}$
2. $|B(T)| = |A(T)| + 1$ since every $v \in T \setminus {r}$ is $M$-Matching Covered, so we can pair up all vertices in $B(T)$ except $r$ with one in $A(T)$.

• Cook - Combinatorial Optimization - Ch 5, Section 5.2, pg 135

• Odd Integer
• Even Integer