Es sei ${\displaystyle {}G=(V,E)}$ ein Graph und ${\displaystyle {}P\subseteq E}$ eine Paarung. Man nennt einen Weg in ${\displaystyle {}G}$ alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus ${\displaystyle {}P}$ und aus ${\displaystyle {}E\setminus P}$ besitzt.