Alternating Paths and Cycles

Alternation Relative to a Matching

A matching records a set of edges with no shared endpoints. Once a matching is fixed, each edge of the graph has one of two statuses: it belongs to the matching, or it does not. A path or cycle is alternating when those statuses switch at every consecutive pair of its edges. This makes the edge pattern itself meaningful: its length and its first and last edges constrain what can happen at its ends.

A path has no repeated vertices; a cycle has no repeated vertices other than its starting and ending vertex. The length of either is its number of edges. A path consisting of one vertex has length zero and no edges, so it has no edge pattern to classify; throughout, an alternating path means one of positive length. Since \(M\) is a matching, no two consecutive edges of any path or cycle can both belong to \(M\). Alternation adds the other requirement: no two consecutive edges can both lie outside \(M\).

A vertex is saturated by \(M\) if it is incident with an edge of \(M\), and unsaturated or exposed if it is not. These terms refer to all of \(M\), not just to the edges used by a particular path. In particular, a path endpoint can be incident with a nonmatching path edge and still be saturated by a matching edge that is not on the path.

Edge Patterns and Path Length

Write the edges of an alternating path in order as \(e_1,e_2,\ldots,e_\ell\). Once the status of \(e_1\) is specified, every later status is determined: \(e_i\) belongs to \(M\) exactly when \(e_{i+1}\) does not, for each \(i<\ell\). Thus the pattern switches at every step.

Proof. Suppose first that the path has even length \(\ell=2k\), where \(k\ge1\). Its positions \(1,2,\ldots,2k\) can be grouped into the \(k\) consecutive pairs \((1,2),(3,4),\ldots,(2k-1,2k)\). In each pair, one edge belongs to \(M\) and one does not, so there are \(k\) edges of each type. Since the statuses switch at every step and there are an even number of edges, the status at position \(2k\) differs from the status at position \(1\). Now suppose \(\ell=2k+1\), where \(k\ge0\). The first \(2k\) positions form \(k\) consecutive pairs, each containing one edge of each type, and the last edge has the same status as the first because \(2k\) switches return to the starting status. Therefore the starting type occurs \(k+1\) times and the other type occurs \(k\) times. This also covers \(\ell=1\), when \(k=0\). \(\square\)

The length-parity rule gives a quick way to check a proposed pattern. For example, a path of length four cannot have both its first and last edges in \(M\): four alternating edges have two of each type and different statuses at the two ends. A path of length three has either the pattern \(M,\ E\setminus M,\ M\), or the pattern \(E\setminus M,\ M,\ E\setminus M\).

There is an important limitation: the first or last edge of a path is only the edge used by the path at that endpoint. If that edge is in \(M\), the endpoint is certainly saturated. If the path edge is outside \(M\), the endpoint may be saturated by a different edge. This distinction is necessary when translating an edge pattern into a statement about vertices.

Proof. An endpoint is incident with exactly one edge of the path. If that edge belongs to \(M\), it is an incident matching edge, which is precisely what it means for the endpoint to be saturated. If both endpoints are unsaturated, each has no incident edge in \(M\), so the first and last path edges are outside \(M\). Alternation then forces the statuses to start and end outside \(M\). By the proposition, an alternating path with the same status at both ends has odd length. \(\square\)

Alternating Cycles

Proof. List the cycle's edges in their cyclic order as \(e_1,e_2,\ldots,e_\ell\), where \(\ell\ge3\). Alternation requires consecutive edges to have different statuses, including \(e_\ell\) and \(e_1\). Starting from the status of \(e_1\), each step switches the status. After \(\ell\) switches, the status must return to that of \(e_1\), because the next comparison is between \(e_\ell\) and \(e_1\). An odd number of switches would give the opposite status, so \(\ell\) is even. With \(\ell=2k\), the cyclic sequence has \(k\) edges of each type: starting at any edge, the statuses alternate \(k\) times through each type. \(\square\)

In an alternating cycle, every vertex is incident with exactly one cycle edge in \(M\) and one cycle edge outside \(M\). The first statement follows by examining the two cycle edges meeting at that vertex: alternation requires opposite statuses. This describes the edges of the cycle; it does not say that the cycle contains every matching edge incident with its vertices in the whole graph.

Worked Examples

Common Pitfall: Confusing Edge Status with Endpoint Status

A nonmatching path edge does not prove that its endpoint is unsaturated. In the second example, the incorrect calculation would be: “The last edge \(34\notin M\), so vertex \(4\) is unsaturated.” That conclusion examines only the path edge and ignores the rest of the matching. The correction is to inspect all edges of \(M\) incident with the endpoint: \(45\in M\) and \(45\) is incident with \(4\), so \(4\) is saturated.

The converse implication is safe: if an end edge of the path belongs to \(M\), the endpoint is saturated. But if the end edge is outside \(M\), the endpoint may be either saturated or unsaturated. Keep the two questions separate: first determine the path's edge pattern; then check the endpoint's incident matching edges in the whole graph.

Alternation is also distinct from the bipartition of a bipartite graph. A bipartition classifies vertices, while a matching classifies edges as selected or not selected. A path may alternate between the two vertex parts and independently alternate between matching and nonmatching edges; the two patterns describe different features.