Alternating plane graphs: settling Conjectures 10.1 and 10.2, with witnesses for 10.3
Settles two of the four open problems, and advances a third in Section 10 of Althöfer, Haugland, Scherer, Schneider & Van Cleemput, Alternating plane graphs, Ars Math. Contemp. 8 (2015) 337–363. Results Problem Status Conjecture 10.1no 2,Y- and no X,2-APG Proved, and not resting on an interpretation. Definition 2.1 is silent about bridges; the paper rules them out a few lines later by asserting that an APG is always 2-edge-connected, “since plane graph with edge connectivity 1 contains a face that is adjacent to itself” (p. 339). The proof here does not use that sentence — it closes under the permissive reading too, in which bridges are allowed. Conjecture 10.2(3,4,5)-APGs for all n ≥ 20 Settled. Certificates for all 26 previously open orders, plus a proved periodic capping lemma generating order 48 and every order n ≥ 50. Together these close every order n ≥ 46 without reference to the source paper; orders 20–45 remain that paper's own heuristic and Section-8 coverage and are not re-established here. Conjecture 10.33-connected APG for all n ≥ 19 Witnesses at 54 orders; the infinite tail is not proved. Verified 3-connected witnesses at 17, 19–56, 67–74, 88–92, 109–110. Orders 57–66, 75–87, 93–108 and every n ≥ 111 rest on a periodic family whose induction was found unproved on 2026-09-05, or on the source paper's own assertion about its Section-8 constructions. Fourth problemasymptotic degree distribution Open. The distribution of v4/v3 on [1, 1.5]. Out of reach of these methods; the deposit explains why. Also included: a (3,4,5)-alternating plane graph on 46 vertices with a separating pair, refuting the natural shortcut that every such graph is 3-connected. Verification Measure Value Gates 1295 passed, 13 skipped of 1308 Runtime about 8 minutes (Python 3.9.6, macOS); about 2 hours if the optional python-sat is installed Dependencies of the settled results Python standard library only Independent verifiers per certificate 4 Run it with make deps && make verify. Certificates store rotation systems only: no file records a claim that a graph is an alternating plane graph, and every derived property is recomputed on each run by three independently written decision procedures. Most gates are paired with a control that must fail. That is not universal: test_verifier_mutations.py lists 17 sites with no negative control, and three coverage gates were found in September 2026 to be reading an empty set. Both are recorded rather than fixed silently. Of the 17, six are the Theorem 3.2 identities and the two alternation clauses are each controlled in the other verifier. Honest limits 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 in this work were false and were withdrawn, plus a certificate misidentified as not 3-connected. All are recorded at the files that made them rather than quietly deleted; see REVIEW.md. 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 digest of every original preserved for verification. AI assistance was substantial, including the step that makes Conjecture 10.1 unconditional. No AI system is an author. See AI_DISCLOSURE.md. Start with ARTIFACT.md; ZENODO.md is a formatted summary of this deposit.