Matching

Last updated Nov 1, 2022

Let $G = (V, E)$ be an Undirected Graph. A Matching is a Set $M \subset E$ so that $\forall u \in V$, $|{e \in M : u \cap e \neq \emptyset}| \leq 1$.

1. For any Undirected Graph $G$, $\emptyset$ is a Matching. Indeed for all $u \in V(G)$, $|{e \in \emptyset : u \cap e \neq \emptyset}| = 0 \leq 1$.
2. TODO

• Matching Alternating Path
• Matching Augmenting Path

• Set Cardinality
• Set Intersection