Alternating plane graphs: settling Conjectures 10.1 and 10.2, with witnesses for 10.3
Section 10 of Althöfer, Haugland, Scherer, Schneider and Van Cleemput leaves four problems open. This deposit settles two and advances a third with verified witnesses at 54 orders; the infinite tail of Conjecture 10.3 is not proved, and the fourth problem remains open.
Abstract
An alternating plane graph is a plane graph of minimum degree 3 and minimum face size 3 in which adjacent vertices differ in degree and adjacent faces differ in size. An X,Y-APG is one realising exactly X distinct degrees and Y distinct face sizes. The 2015 paper of Althöfer, Haugland, Scherer, Schneider and Van Cleemput introduces these graphs and closes with four open problems.
This deposit settles two of them and advances a third. The results below are stated as they are proved: Conjecture 10.1 is a theorem; Conjecture 10.2 is settled in the sense its statement asks for — an explicit alternating plane graph at every order it claims one for, each witness re-verified from its rotation system rather than asserted; Conjecture 10.3 is not settled here, and carries witnesses at 54 orders with the tail above 56 left open.
| problem | statement | status |
|---|---|---|
| Conjecture 10.1 | No 2,Y-APG and no X,2-APG exists | Proved, and again for the bridge-relaxed definition. |
| Conjecture 10.2 | A (3,4,5)-APG exists at every order n ≥ 20 | Settled. The 26 open orders certified; the rest is the 2015 paper’s, and a proved capping lemma re-proves every n ≥ 67 |
| Conjecture 10.3 | A 3-connected APG exists at every order n ≥ 19 | Witnesses at 54 orders. The infinite tail is not proved — see below |
| Fourth problem | The asymptotic distribution of v₄/v₃ | Open. Out of reach of these methods |
Conjecture 10.1, and the bridge convention
The proof is a counting argument over edges — a single per-edge inequality applied twice. It turns on how the definition behaves at a bridge, where the same face lies on both sides of the edge, so "adjacent faces differ in size" is either violated at every bridge or vacuous at every bridge.
The paper settles this, and we should be clear that it does. Definition 2.1 itself lists four conditions and says nothing about bridges, but a few lines further down (p. 339) the authors assert that an alternating plane graph "is always at least 2-edge-connected, since plane graph with edge connectivity 1 contains a face that is adjacent to itself." That is the strict reading, stated as a consequence in passing rather than proved or written into the definition.
The argument here does not lean on that sentence. It closes under the permissive reading as well, in which bridges are allowed, by way of a parity lemma — for any plane graph whose faces admit a proper 2-colouring, deg(v) − bridges_at(v) is even — which pins each degree-3 endpoint onto exactly one bridge and lets the count close with room to spare.
The slack is measured rather than asserted: the argument still closes when the bridge-face bound is weakened from 8 to 7, and fails at 6.
Conjecture 10.2: the orders that were open
Conjecture 10.2 was open at exactly 26 orders. All now carry certificates.
| block | orders open |
|---|---|
| 46–56 | 11 |
| 67–74 | 8 |
| 88–92 | 5 |
| 109, 110 | 2 |
A finite list would settle the conjecture only up to the largest order in it. It is therefore accompanied by a proved periodic capping lemma: one certificate per residue class mod 3, at orders 67, 68 and 69, splices into an arbitrarily long periodic strip, generating a (3,4,5)-APG at every order n ≥ 67. Above that, the lemma removes any dependence on the list.
What is established here, and what is inherited
Worth stating precisely, because “settled” can cover a weaker claim than it sounds. The conjecture closes as a union of four ranges, and three of them are the 2015 paper's: its heuristic search (20–42), its Section-8 construction, and its Theorem 8.1 (n ≥ 111). Only the 26 certified orders are new.
Taking the certificates together with the capping lemma and nothing else, this deposit closes orders 46 to 56 and every order n ≥ 67 on its own — which makes the paper's Theorem 8.1 redundant. Orders 20 to 45 and 57 to 66 are inherited from its heuristic search and Section-8 construction and are not re-established here.
The capping lemma is proved for inserting periods. Deleting periods also yields machine-checked graphs at orders 57 to 66, but that direction is not proved, and those orders are counted as inherited.
A counterexample worth having
The natural shortcut from 10.2 to 10.3 is to hope every (3,4,5)-APG is already 3-connected. It is not. The deposit contains a (3,4,5)-alternating plane graph on 46 vertices with a separating pair, which refutes that and is why Conjecture 10.3 needs witnesses of its own.
Conjecture 10.3, and a claim we had to withdraw
This one was published as settled, and on 5 September 2026 an adversarial review showed that was too strong. It is worth stating plainly, because it is the largest correction this deposit has had to make.
What holds. Verified 3-connected witnesses exist at 54 orders: 17, 19–56, 67–74, 88–92 and 109–110. Each is checked from its own rotation system, and none of them depends on the argument below.
What does not. The remaining orders — 57–66, 75–87, 93–108 and every n ≥ 111 — were carried by an induction over the periodic family. That induction's key step assumes the connectivity it is supposed to prove: it shows a freshly spliced copy attaches to both sides, where what is needed is that the graph stays connected after the separating pair is already removed. A second step, that the splice point can always be moved clear of the pair, is an off-by-one asserted rather than checked.
There is an alternative route — the source paper states that its own Section-8 constructions are 3-connected, and those cover exactly the gaps. But that is an assertion in a concluding bullet rather than a theorem, and it is hedged elsewhere in the same sentence. Using it would substitute an inherited unproved claim for a local one. Better, but not a repair.
What the certificates actually contain
Rotation systems, and nothing else. No file in the deposit records a claim that a graph is an alternating plane graph. Degrees, faces, face sizes, bridges, connectivity and both alternation conditions are recomputed on every run by four independently written decision procedures, and most gates are paired with a control that must fail. Not all: 17 sites have no negative control, and in September 2026 three coverage gates were found to be reading an empty set. Both are recorded rather than fixed quietly. Of the 17, six are the Theorem 3.2 identities, two are a restriction the definition does not impose, and the two alternation clauses are each controlled in the other verifier — every certificate goes through both.
Reproducing it
git clone https://github.com/SeverinVisionary/alternating-plane-graphs cd alternating-plane-graphs make deps # pytest, and nothing else make verify-fast # load-bearing gates, about a minute make verify # everything, about 8 minutes
1295 passed, 13 skipped on Python 3.9.6, macOS. Nothing the settled results depend on needs a package outside the standard library. The 13 skips are declared rather than hidden: 11 need a third-party corpus that is not redistributed here, one needs the optional python-sat, and one follows from the first.
What is not established
- The fourth problem stays open. It asks for the limiting density of v₄/v₃ on the interval [1, 1.5] — a distributional question, not a counting one, and nothing here bears on it. The ratio measured across the 26 certificates lands in [1.000, 1.125] and drifts toward 1, but those graphs were selected by the search that found them, so that number is a selection effect and not evidence. It is written up as a caution, not a result.
- The manuscript in paper/ compiles and ships as an 11-page PDF, but it is a draft that has had no peer review.
- Three claims made during this work were false and were withdrawn, and one certificate was misidentified as not 3-connected. All four are recorded at the files that made them rather than quietly deleted.
- No third-party bytes are redistributed. No licence statement was found at the source of the published corpus, so each of its graphs is re-expressed in this repository's own format, with the SHA-256 of every original preserved so the re-expression can be checked against it. Re-encoding changes the bytes, not the provenance: the MIT licence is not asserted over those graphs, and the corpus authors have not been contacted.
- The three verifiers are independent of each other but were written against one reading of the definition. A misreading would be confirmed unanimously rather than caught. The bridge convention above is handled explicitly; the rest of the definition rests on the author's reading of the source.
- No human has peer-reviewed this work. AI assistance was substantial, including the step that extends Conjecture 10.1 to bridge-relaxed graphs. No AI system is an author.
Read further
- ARTIFACT.md — what is here and how to check it
- ARTIFACT.md as a PDF — a typeset rendering of the artifact overview, unchanged in content; its first page names the commit it was rendered from. The manuscript in paper/ is a separate document, compiled as its own PDF, and is not what this rendering contains
- CONJECTURE_10_1.md — the per-edge inequality and the bridge case in full
- DENSITY.md — the fourth problem, and why it is out of reach here
- REVIEW.md — the withdrawn claims, kept in place
- AI_DISCLOSURE.md — which systems did what
- Zenodo archive — versioned, with every certificate