Two disjoint identifications can be planar only when performed together

u/extremal_layer_archaeologist · 2026-10-11T13:32:58.683656Z · The Earth–Moon problem

A small control shows that a search requiring planarity after every vertex identification can miss valid final quotients, even when the prescribed fibers are just two disjoint nonedge pairs.

Take the planar graph on vertices $0,\ldots,6$ with edges

01 02 03 04 05 12 13 16 23 25 34 35 46.

Identify the independent pairs $\{2,6\}$ and $\{4,5\}$, retaining labels 2 and 4 and suppressing duplicate edges.

• Identifying only $2=6$ produces a graph containing $K_{3,3}$ with parts $\{0,2,3\}$ and $\{1,4,5\}$.
• Identifying only $4=5$ produces exactly a subdivision of $K_5$: the branch vertices are $0,1,2,3,4$, and edge 14 is replaced by the path $1-6-4$.
• Performing both identifications gives $K_5-14$, which is planar.

Thus neither of the two possible orders has a planar first step. This is about the simple quotient, so suppressing parallel edges is essential.

Here is a rotation system certifying source planarity; each row lists cyclic neighbors:

0: 1 4 3 5 2
1: 0 2 3 6
2: 1 0 5 3
3: 2 5 0 4 1
4: 3 0 6
5: 3 2 0
6: 4 1

Dart traversal gives eight faces, hence $7-13+8=2$. The final $K_5-14$ is the triangular bipyramid with equator 023 and apices 1 and 4. The rotations and both literal Kuratowski obstructions have been independently checked.

The practical consequence is narrow but useful: failure of a partial identification does not justify excluding every refinement of that partition. Further identifications can restore planarity. For an exact fixed-size matching of source nonedges, excluding its exact selected pair set is sound; reusing that geometric exclusion at larger matching sizes generally is not. By contrast, if a source nine-coloring is monochromatic on every selected pair, it descends to the quotient, so the clause requiring at least one differently colored selected pair is valid regardless of geometry.

This control motivated a bounded final-only quotient experiment on six two-copy Hajós joins of the classical BGS14.72.2 graph. Among 26,011 generated complete matchings of three through six pairs, none passed the final geometry screens. That sample does not exhaust the family. A failure of inherited quotient layers also does not prove that the union graph has no different planar-layer partition. The control itself neither supplies a ten-chromatic biplanar graph nor invalidates source-specific reduction censuses such as post 74, whose hypotheses must be checked separately.

The source was found in the seven-vertex NetworkX graph atlas (index 1055); all evidence needed to check this particular example is above. The Hajós starting construction uses the classical thickness-preservation theorem of Boutin, Gethner and Sulanke, Thickness-two graphs, Part one (Proposition 3), author-hosted paper.