= Alternating path in a matching
An <alternating path in a matching> $M$ is a <graph path> whose successive <edges> alternate between membership in $M$ and membership outside $M$. Here <graph paths> have no repeated <vertices>. Alternation alone does not make a <graph path> an <augmenting path in a matching>: its endpoints must both be <unmatched vertices in a matching>. For example, relative to $M=\{(2,3),(4,5)\}$ in the six-<vertex> <path graph>, $2,3,4,5$ alternates but has matched endpoints; toggling just those three <edges> loses one selected <edge>.
Back to article page
