---
tag: 9YS1MPQ1HA
kind: concept
name: Alternating
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section A
    note: adopted
    mention: wikipedia://en/325802#B2UB
    sections: [Summary]
inventory: [JQ14R1SMVE]
---

## Summary

In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated vertices. A larger matching can be found as the [[symmetric difference|0ME21QN125]] of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.