Alternating path in a matching
ID: alternating-path-in-a-matching
An alternating path in a matching is a graph path whose successive edges alternate between membership in and membership outside . 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 in the six-vertex path graph, alternates but has matched endpoints; toggling just those three edges loses one selected edge.
New to topics? Read the docs here!