# Verification report — OWR-12861-021 (Heinig, Oberwolfach Report 01/2014, Question 2)

Verification date: 2026-09-28.

**Verdict.** Negative answer to the question as stated, for every odd n ≥ 7 under both natural readings of
"periphery", and for n = 9 under every reading. Complete elementary proof; unrefereed.

## Statement checked
- Source: Oberwolfach Reports 11 (2014), no. 1 (Report 01/2014, *Combinatorics*, organisers J. Kahn,
  A. Steger, B. Sudakov), problem session, contribution of P. Heinig, pp. 81–82, DOI 10.4171/OWR/2014/01.
  The text was read from a local copy of the report.
- Heinig's Question 2 asks whether, for every odd n ≥ 7, every n-vertex graph with minimum degree at least
  ⌈n/2⌉ contains a spanning copy of the graph obtained from the square of the n-cycle by deleting "every
  other edge on the periphery" until exactly three consecutive vertices of degree 4 remain. He notes that
  a positive answer would imply a positive answer to his Question 1, the Hamilton-generation question.
- The corpus record (ulamai/UnsolvedMath, OWR-12861-021, status `partially_solved`) states the same
  question. Its literature note concerns Question 1, not Question 2.
- The garbled glyphs in the extracted text were decoded from the raw bytes: `\x15` in the TeX symbol font
  is ≥, so the source says n ≥ 7; `d … e` is ⌈ ⌉.

## Readings of "periphery"
- **(R1)**, the periphery is the n-circuit. This is the intended reading. For even n, deleting every
  other edge of the n-circuit from C_n² leaves exactly the prism C_{n/2} □ K_2, which is the setting of
  Heinig's paper (European J. Combin. 36 (2014) 503–530).
- **(R2)**, the periphery is the boundary of the triangulated Möbius band C_n² (odd n). Included for
  robustness.
- **Broadest reading.** Every reading deletes a matching of size (n−3)/2 from C_n².
  - If an arbitrary Hamilton cycle of C_n² may serve as the periphery, G_7 contains one of the resulting
    graphs, namely C_7² − {01, 35}.
  - But K_{4,4,1} (minimum degree 5) contains none of the 177 graphs C_9² − M. So the universal question
    fails at n = 9 under every reading.

## Proof obligations checked
- Reduction: a spanning copy maps an independent (n−1)/2-set J of H onto the independent side B of G_n.
  Then H − J must embed into G_n[A], and e(H − J) = 3 − |J ∩ {degree-4 vertices}|.
- (R2): H'_n contains the n-cycle, so an independent (n−1)/2-set is an alternating set. It contains
  s − 1 ≥ 2 consecutive periphery edges, and at most every other one of these is deleted. This needs
  n ≥ 7. At n = 5 the edge count, 9 against 8, still excludes an embedding.
- (R1): the run/gap classification of the independent sets, checked line by line in both residue
  classes n ≡ 1 and n ≡ 3 (mod 4), including the wrap-around. The leftover H − J is a path with two
  edges (n ≡ 3) or a triangle (n ≡ 1), neither of which fits into G_n[A].
- The host G_n has minimum degree exactly ⌈n/2⌉, including the case where G_n[A] contains P_3.

## Computations (exact; scripts and outputs in reproducibility/)
- Claimant, `verify_heinig_q2.py`:
  - degree sequences;
  - brute force over all bijections for n = 7, 9;
  - complete enumeration of the independent (n−1)/2-sets for odd 7 ≤ n ≤ 61;
  - SAT for 7 ≤ n ≤ 25.
- Independent referee (code written from scratch), `audit_core.py`, `audit_readings.py`, `audit_k441.py`:
  - structural test for odd 5 ≤ n ≤ 101;
  - a second SAT encoding (7 ≤ n ≤ 61);
  - backtracking (7 ≤ n ≤ 25) and VF2 (7 ≤ n ≤ 13), with positive controls;
  - uniqueness of each reading up to isomorphism;
  - Heinig's graph X ≅ G_7;
  - broad-reading tests;
  - the K_{4,4,1} statement.
- Lead auditor, `lead_checks.py`:
  - X ≅ G_7 and G_7 ⊇ C_7² − {01, 35};
  - the K_{4,4,1} statement;
  - for n = 7 and 9, every graph with minimum degree ⌈n/2⌉ + 1 contains H_n (complements of maximum
    degree ≤ 1, resp. ≤ 2, all up to isomorphism). So the threshold for (R1) is exactly ⌈n/2⌉ + 1 for
    these n.

## Independent adversarial audit
Verdicts (2026-09-28): statement fidelity CONFIRMED; proof CONFIRMED_WITH_FIXES; answers the question as
posed CONFIRMED_WITH_FIXES; novelty CONFIRMED_WITH_FIXES. The fixes were incorporated in the paper:
- the reading R1 is justified;
- the n = 5 overreach is removed;
- G_7 is identified with Heinig's graph X;
- the broadest reading is discussed;
- the missing literature is added;
- the DOI and page numbers are corrected.

## Relation to the literature, novelty and scope
- **Question 1** was settled for large odd n by Christoph–Nenadov–Petrova (minimum degree n/2 + C; J.
  Combin. Theory Ser. B 176 (2026)) and Hou–Yin (arXiv:2503.15950: Hamilton-connected graphs with minimum
  degree ≥ (n−1)/2 are Hamilton-generated). The negative answer to Question 2 does not affect this,
  because Question 2 only implies Question 1.
- **G_7 is Heinig's graph X.** It is the graph of Definition 28 and Proposition 30 in arXiv:1112.5101,
  his own positive example for Question 1.
- **Searches.** The arXiv API, Crossref, OpenAlex (works citing Heinig 2014), Semantic Scholar and web
  searches found no work that states, discusses or answers Question 2. The HTML full texts of the
  follow-up papers were checked: Christoph–Nenadov–Petrova, Hou–Yin, and Hefetz–Krivelevich
  arXiv:2506.19731, 2507.04488 and 2606.05835.
- **Residual gap.** Heinig's 2014 TU München dissertation could not be consulted.
- This negative search is not a proof of priority, and no priority claim is made.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/