Symmetric Differences of Matchings

Comparing Two Matchings by Their Edges

Two matchings can overlap, or they can choose different edges in parts of the same graph. Comparing their sizes directly tells us which has more edges, but not where the difference comes from. The symmetric difference isolates precisely the edges that belong to one matching but not both. Its components have a simple structure, and that structure explains the difference in size.

Throughout, \(G=(V,E)\) is a finite simple graph. A matching is a set of edges no two of which share an endpoint. A vertex incident to an edge of a matching is saturated by that matching; otherwise it is unsaturated. For two sets of edges \(M\) and \(N\), their symmetric difference consists of the elements in exactly one of the sets.

View \(H=(V,M\triangle N)\) as a graph on the same vertices as \(G\), using only the edges in the symmetric difference. Some vertices of \(H\) may be isolated. When we discuss its path and cycle components, we mean its components containing at least one edge; isolated vertices contribute no edges and have no effect on matching sizes.

The Structure of the Symmetric Difference

Proof. Let \(H=(V,M\triangle N)\). At any vertex \(v\), there is at most one incident edge of \(M\), since \(M\) is a matching, and at most one incident edge of \(N\). Every edge of \(H\) belongs to exactly one of \(M\setminus N\) or \(N\setminus M\). Therefore \(\deg_H(v)\le 2\). If \(\deg_H(v)=2\), one incident edge must belong to \(M\setminus N\) and the other to \(N\setminus M\): two edges from the same one of these sets would violate the matching condition for that matching.

Now consider a connected component of \(H\) containing an edge. If it has a vertex of degree 1, start there and follow its edge. At each later vertex, there is at most one edge other than the edge just used, so continue along that edge if it exists. The walk cannot repeat a vertex: a repetition would produce a cycle, and the repeated vertex would then have two cycle edges as well as the initial route from the degree-1 vertex, contradicting the degree bound or the choice of the first repetition. Since the component is finite, the walk ends at a vertex of degree 1. No vertex of the component can be outside this path, because connectedness would require an additional edge meeting the path, which would give one of its vertices degree at least 3 or allow the traversal to continue. Thus the component is a path.

If the component has no degree-1 vertex, every vertex in it has degree 2: it is connected, contains an edge, and has no isolated vertex. Start at any vertex and follow edges, always taking the edge other than the one just used. Finiteness forces a repeated vertex; because every vertex has degree 2, the first repetition closes a cycle. Every vertex on that cycle already has its two incident edges in the cycle, so connectedness leaves no vertex of the component outside it. Thus the component is a cycle. At each degree-2 vertex the two incident edges belong to different matchings, as shown above. Consequently, edges alternate along every path or cycle obtained. On a cycle, alternating between two edge sets and returning to the starting edge type requires an even number of edges. Hence every cycle component has even length. \(\square\)

This theorem uses the matchings separately: each can contribute at most one edge at any vertex. It does not say that the union \(M\cup N\) has the same structure, since an edge common to both matchings can give a vertex more incident edges in the union.

How the Components Determine the Size Difference

Proof. Edges in \(M\cap N\) contribute one to both \(|M|\) and \(|N|\), so they cancel in \(|M|-|N|\). Edges outside \(M\triangle N\) belong to neither matching. Thus the difference is the total number of \(M\setminus N\) edges minus the total number of \(N\setminus M\) edges, counted over the edge-containing components of \(H\). In an alternating cycle, the even number of edges divides equally between the two matchings, so the contribution is zero. In an alternating path, the edge types alternate. If its length is even, the two types occur equally often and the contribution is zero. If its length is odd, one type occurs once more than the other, so the contribution is \(1\) or \(-1\). This proves the formula and the stated possibilities. \(\square\)

More specifically, an odd-length path contributes \(1\) when both end edges belong to \(M\setminus N\), and \(-1\) when both belong to \(N\setminus M\). An even-length path has different matching types at its two ends and contributes zero. These statements concern edges in the path, not whether its endpoint vertices are saturated by other edges outside the symmetric difference.

A Common Mistake

Wrong calculation: In the previous example, one might use the union \(M\cup N=\{ab,cd,de,fg,gh,hi,xy\}\) and treat it as one alternating structure. That is not the symmetric difference: it includes \(ab\), which belongs to both matchings. Moreover, the union has three edges incident to \(g\) or \(h\) taken together (\(fg,gh,hi\)); the degree-two structure proved for the symmetric difference does not apply to the union in general.

Correction: First remove the common edges by forming \((M\setminus N)\cup(N\setminus M)\). Here \(ab\) is removed, leaving the three alternating components listed above. Only then count each component’s \(M\)-edges and \(N\)-edges. The component counts give \(0+1-1=0\), consistent with the direct size difference \(4-4=0\).

The component formula is useful because it localizes a comparison: cycles and even-length alternating paths cannot change the difference in size, while odd-length paths account for any imbalance. This is a structural fact about two matchings, not by itself a test that either matching is maximum. In particular, the existence of a path component with one more edge from \(M\) does not alone establish that \(M\) is maximum; it only describes the comparison between the given \(M\) and \(N\).