交互道・増加道

$M$ をマッチングとする。道 $P=x_0x_1\cdots x_k$ が $M$-交互道であるとは、辺 $x_{i-1}x_i$ が $M$ に属するものと属さないものが交互に並ぶことをいう。両端点 $x_0\ne x_k$ がどちらも $M$ で非飽和な $M$-交互道を $M$-増加道という。