The intersection of two perfect matchings

The intersection of two perfect matchings

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless cubic multigraph with no bridge. A perfect matching $M\subseteq E$ meets every vertex in exactly one incident edge. For a nonempty proper set $X\subset V$, the edge cut $\delta_G(X)$ consists of all edges with one endpoint in $X$ and the other outside $X$. An odd edge cut is such a cut of odd cardinality; minimality as an edge cut is not required.

The conjecture asks for two perfect matchings $M_1,M_2$ such that their intersection contains no entire odd cut. Precisely, the required condition is \[ \delta_G(X)\not\subseteq M_1\cap M_2 \quad\text{whenever }|\delta_G(X)|\text{ is odd}. \] Thus every odd cut must have at least one edge absent from one of the matchings. The matchings need not be disjoint, and the assertion does not require their intersection to avoid every edge of every odd cut.

In a cubic graph the identity $3|X|=2|E(G[X])|+|\delta_G(X)|$ shows that cut size is odd exactly when $|X|$ is odd. Moreover, each perfect matching meets such a cut an odd number of times, because $|X|=2|M\cap E(G[X])|+|M\cap\delta_G(X)|$. The problem is to choose the two matchings simultaneously so these unavoidable cut intersections never include all edges of one odd cut in common.

Short English statement

Can two perfect matchings of every bridgeless cubic graph be chosen so that their common edges contain no complete odd edge cut?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Literature and conventions.

The original entry [S2] asks that the intersection contain no entire odd cut. It does not require that the intersection avoid every edge lying in an odd cut. We retain that distinction and work with finite loopless cubic multigraphs, treating parallel edges separately. The following reduction translates the obstruction into component parity, making the relevant condition directly verifiable. The Garden entry also relates this question to matching and postman-join formulations; we establish the particular equivalence needed here explicitly.

A component-parity criterion.

For two perfect matchings $M_1,M_2$, put $A=M_1\cap M_2$, and let $G-A$ retain all vertices. Then \[ A\text{ contains no odd edge cut} \quad\Longleftrightarrow\quad \text{every component of }G-A\text{ has even order}. \tag{1} \] Indeed, cubic degree summation gives \[ |\delta(X)|\equiv |X|\pmod2. \tag{2} \] If a component $X$ of $G-A$ has odd order, every edge leaving it belongs to $A$, and $2$ makes its boundary an odd cut. Conversely, if $\delta(X)\subseteq A$, then no edge of $G-A$ crosses between $X$ and its complement. Thus $X$ is a union of components of $G-A$. If all these components have even order, $|X|$ and hence $|\delta(X)|$ are even. This proves $1$, including disconnected graphs. In particular, testing only the components suffices; one need not enumerate exponentially many vertex subsets.

Constructing the corresponding odd-degree edge set.

For completeness, $1$ is also equivalent to existence of an edge set $J\subseteq E(G)\setminus A$ having odd degree at every vertex. Necessity follows because the sum of degrees inside a component of $G-A$ is even, so its number of odd-degree vertices is even. For sufficiency, choose a spanning tree in each even-order component and root it. For each nonroot vertex $v$, include its parent edge in $J$ exactly when the rooted subtree at $v$ has odd order.

To verify the degrees, write $s_v$ for the parity of that subtree's order. If the children of $v$ are $w$, then \[ s_v\equiv1+\sum_w s_w\pmod2. \] A nonroot vertex has selected-edge degree congruent to $s_v+\sum_w s_w=1$. At a root, the whole component has even order, so $0=1+\sum_w s_w$; its selected-edge degree is also odd. This constructs $J$ without relying on an unproved matching theorem. Since $G$ is cubic, $E(G)\setminus J$ then has even degree at every vertex. The construction proves the certificate equivalence, but does not manufacture a suitable pair $M_1,M_2$.

Two sufficient conditions for the desired pair.

First, if $G$ is bridgeless and $|M_1\cap M_2|\le2$, their intersection cannot contain an odd cut. A nonempty odd cut has size at least one; a cut of size one is a bridge, so in a bridgeless graph its size is at least three.

Second, suppose there are three perfect matchings $M_1,M_2,M_3$ with empty triple intersection. If an odd cut were contained in $M_1\cap M_2$, parity forces $M_3$ to contain an edge of that cut, contradicting empty triple intersection. Consequently any three matchings from a Berge--Fulkerson six-cover give a suitable first pair: each edge belongs to exactly two of the six indexed matchings, so no three have a common edge. Repetitions in the indexed family do not invalidate this argument.

Verification and the missing step.

On the Petersen presentation $a_i a_{i+1},a_i b_i,b_i b_{i+2}$, the spoke matching and \[ \{a_0b_0,a_1a_2,a_3a_4,b_2b_4,b_1b_3\} \] intersect in the single edge $a_0b_0$, so the first sufficient condition applies. The companion script scripts/check_attempt_batch02_graphs_2026_10_01.py verifies the matchings and checks every vertex cut of this ten-vertex graph, together with its component parities after deleting that intersection.

For arbitrary bridgeless cubic graphs, choosing $M_2$ to keep all components of $G-(M_1\cap M_2)$ even is exactly the unresolved selection problem. A spanning-tree construction of $J$ helps only after this parity condition has been achieved; reversing that dependency would be circular.

Final status.

The certificate equivalence, constructive odd-degree witness, and the stated sufficient conditions are proved. Existence of the required matching pair for every graph in the catalogue is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3180 (OPG-543), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The intersection of two perfect matchings. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/intersecting_two_perfect_matchings.