# Verification report — OWR-1782-009 and OWR-1386-013 (the all-n exact codegree conjecture for tight Hamiltonian cycles)

Verification date: 2026-09-28.

**Verdict.** Negative answer as stated. The statement "every k-graph on n ≥ k+1 ≥ 4 vertices with minimum
codegree at least ⌊(n−k+3)/2⌋ has a tight Hamiltonian cycle" is false for small n. The smallest counterexample is
H_3: an apex joined to all 15 pairs of a 6-set W, plus the 10 faces of the hemi-icosahedron on W. It has 7 vertices,
25 edges and minimum codegree 3 = ⌊7/2⌋, and no tight Hamiltonian cycle. The large-n statement is not affected.
Unrefereed.

## Statement checked
- **Sources.** Both were rendered and read on the printed pages.
  - Oberwolfach Reports 5 (2008), no. 1 (Report 01/2008, *Combinatorics*), A. Ruciński (joint with V. Rödl and
    E. Szemerédi), "Dirac type results for uniform hypergraphs", pp. 46–47, DOI 10.4171/OWR/2008/01. Conjecture 1:
    n ≥ k+1 ≥ 4, codegree ⌊(n−k+3)/2⌋, tight cycles. This is the source of OWR-1782-009.
  - Oberwolfach Reports 3 (2006), no. 4 (Report 48/2006), A. Ruciński, "Hamilton cycles and perfect matchings in
    hypergraphs", p. 2928, DOI 10.4171/OWR/2006/48. The same bound, tight cycles, and no range of n. This is the
    source of OWR-1386-013.
- **The standard citation.** Rödl–Ruciński–Szemerédi, Adv. Math. 227 (2011), Conjecture 1.1, has the same all-n
  form. It was read in the 2009 preprint. The conjecture is attributed to Katona and Kierstead. Rödl and
  Ruciński (2010) say that Katona and Kierstead conjectured it implicitly. Liu–Liu (arXiv:2104.05016,
  Conjecture 1.1) repeat the all-n form. Lu–Yuan (arXiv:2607.09245) state the bound (n−k+3)/2 without the floor.
- **Corpus records.** ulamai/UnsolvedMath, OWR-1782-009 (status `partially_solved`) and OWR-1386-013. Both match
  their sources. OWR-1386-013 drops the word "tight". Under a Berge reading these examples are not
  counterexamples.

## Readings
| Reading | Refuted? | Witness |
|---|---|---|
| ⌊(n−k+3)/2⌋ for all n ≥ k+1 ≥ 4 (OWR 2008, RRS 2011, Liu–Liu) | yes | (3,7) H_3; (3,9); (4,8) H_4; (5,9) H_5; (5,10) |
| the same with no range of n (OWR 2006) | yes | the same |
| (n−k+3)/2 without the floor (Lu–Yuan's wording) | yes | only (5,10), with codegree 4 = (10−5+3)/2 |
| k = 3, pair-degree greater than n/2 | no, for n ≤ 9 | raising the bound by one is unsatisfiable at (3,7) and (3,9) |
| the large-n statement | no | proved for k = 3 (RRS 2011); announced for all k ≥ 3 (Letzter–Lang–Ranganathan–Sanhueza-Matamala, reported in arXiv:2609.08613) |

## Proof (in the paper)
- **(F0)** D′ is a 2-(6,3,2) design.
- **(F1)** The complement of each face of D′ lies in D, the family of the other ten triples. So neither D′ nor D
  contains two disjoint triples.
- **For H_3.** In a cyclic order a, w_1, …, w_6, the windows w_1w_2w_3 and w_4w_5w_6 are disjoint triples of W.
  Both would have to be faces of D′, which (F1) rules out.
- **For H_4 and H_5.** A cyclic order is a tight Hamiltonian cycle if and only if every 4-window with exactly one
  apex has its three points of W in D. For every placement of the k−2 ≤ 3 apexes, a short argument on the gap
  vector forces a complementary pair τ_i, τ_{i+3} of W-consecutive triples. (F1) rules this out.
- **Simplification.** This is simpler than the finder's original argument. The finder also used a fact (F2),
  that no tight path on six points lies in D; (F2) follows from (F1) and is not needed.

## Computations (exact; scripts and outputs in reproducibility/)
- **H_3, H_4, H_5.** Minimum codegree 3. No tight Hamiltonian cycle among all 360, 2520 and 20,160 cyclic orders,
  checked by three independent programs.
- **(3,9) and (5,10).** Checked by three independent programs, using exhaustive enumeration and depth-first
  search.
  - (3,9) has 50 edges and minimum pair-degree 4.
  - (5,10) has 191 edges and minimum codegree 4.
  - A second, independent (5,10) example has 186 edges.
- **Minimality.** Every k-graph with n ≤ 6 that meets the bound has a tight Hamiltonian cycle (exhaustive, all k).
  So 7 vertices is the minimum.
- **n = 7, k = 3 (SAT).** 2709 labelled counterexamples in 6 isomorphism classes, with 22–25 edges. H_3 is the
  unique 25-edge class. |Aut H_3| = 60, and Aut H_3 ≅ A_5.
- **SAT census.** Two encodings and two solvers (CaDiCaL and Glucose) agree.
  - Counterexamples exist for (3,7), (3,9), (4,8), (5,9) and (5,10).
  - None exist for (3,4–6), (3,8), (4,5–7), (4,9), (5,6–8), (6,7–9) and (7,8–10).
  - (3,10), (4,10) and (6,10) are undecided.
  - Unsatisfiability results carry no proof certificates.
- **Thresholds (one search only).** At each of the five failing pairs, raising the bound by one gives no
  counterexample.

## Independent adversarial audit
Verdicts (2026-09-28):

| Item | Verdict |
|---|---|
| Statement fidelity | CONFIRMED_WITH_FIXES (attribution: the all-n form is RRS 2011 Conjecture 1.1, attributed to KK; wording of the readings) |
| Proof / computation | CONFIRMED (reproduced with independent code; no errors) |
| Answer as posed | CONFIRMED_WITH_FIXES (status text must not claim the large-n form as proved for all k) |
| Novelty | CONFIRMED, as far as can be checked |

The lead auditor re-checked everything once more: the design facts, Lemmas 2.3 and 2.4 (all 83 gap vectors), H_3,
H_4, H_5, the example files, edge-maximality of H_3, the fact that H_6 has a tight Hamiltonian cycle, and the
Katona–Kierstead construction at small n.

## Relation to the literature, novelty and scope
- **Searches.** In September 2026 we searched arXiv, Crossref, OpenAlex, Semantic Scholar and zbMATH, including the
  reviews of the ten works that zbMATH lists as citing Katona–Kierstead, and the web. We also read the surveys and
  later papers. None reports small-n counterexamples or uses the hemi-icosahedron in this context.
- **The mechanism is classical.** An apex over a base with no tight Hamiltonian path is also the device behind the
  Katona–Kierstead lower-bound construction. What is new is the base D′.
- **Caveats.** The Katona–Kierstead paper (J. Graph Theory 1999) was not read directly; its content is known from
  Rödl–Ruciński (2010) and Katona's later accounts. The published versions of the RRS papers were not read; the
  preprints were. This negative search is not a proof of priority.
- **Scope.** The failures are small-n boundary effects. All known examples have n ≤ k², and each misses by one
  unit. The asymptotic conjecture is not affected. The note does not claim to disprove the Katona–Kierstead
  conjecture.

## 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/