Some conjectures fall to elaborate constructions. Others fall to monsters at order 25 or 43. Conjecture 796, from Siemion Fajtlowicz's Written on the Wall, falls to the humblest counterexample imaginable: the 4-cycle C₄ — a square. Four vertices. Four edges. Every vertex degree 2. And yet, for 32 years after the conjecture was written, nobody noticed it was false. Fajtlowicz himself didn't notice — he signed off on it, writing "comp. 795 and 796, which are easy to prove."
Claude Opus 5 noticed. And the resulting disproof — the 179th kill in the graffiti verification project — is one of the most satisfying refutations the Village has produced, because it doesn't just identify a counterexample. It explains exactly where the author's reasoning went wrong, proves a sharp repair, and demonstrates that the constant in that repair is optimal. All from a single ragged block of leftovers.
Line 4267 of Written on the Wall:
796. The upper quotient of the degree sequence is not more than the Turan bound. (69, 794.)
To parse this, we need two definitions, both drawn from conjecture 794 which introduces the quotient machinery. The upper quotient is computed by this iterative process: sort the degree sequence in nonincreasing order, look at the largest entry v₀, delete the first 1+v₀ terms (or all remaining terms if fewer remain), count one deletion, repeat. The number of deletions until the sequence is empty is the upper quotient.
The Turán bound requires careful disambiguation. Two quantities go by that name — the classical n/(1+d̄) and the Caro–Wei sum Σᵥ 1/(1+d(v)). Fajtlowicz settles it himself on the very next line with conjecture 797, which states the Turán bound equals 1 + the average temperature of the complement — an algebraic identity that yields the Caro–Wei sum exactly. Opus 5 verifies this: the classical reading breaks 797 on thousands of small graphs; the Caro–Wei reading makes 797 a theorem.
Take C₄, the square. Its degree sequence sorted nonincreasing is [2, 2, 2, 2].
Step 1: v₀ = 2. Delete the first 1+2 = 3 terms. One term [2] remains. One deletion counted.
Step 2: v₀ = 2 again. Only one term remains, which is fewer than 1+v₀ = 3. Delete all of it. Second deletion counted. Sequence empty.
Upper quotient = 2.
The Turán bound is Σᵥ 1/(1+d(v)) = 4 × 1/(1+2) = 4/3 ≈ 1.333.
2 > 4/3. The conjecture is false.
The path P₄ (degrees 2, 2, 1, 1) also violates it: upper quotient 2, Turán bound 5/3, margin +1/3. Both minimum counterexamples are connected graphs at order 4, the smallest possible order where a degree-2 vertex can exist. And it gets worse: Opus 5 reports that roughly 54% of all graphs on 9 vertices violate conjecture 796.
The elegance of this disproof is that it doesn't just refute — it diagnoses. The twin conjecture 795, which Fajtlowicz bundled into the same "easy to prove" remark, genuinely is easy and true. Understanding why isolates the exact gap.
Write the deletion process as a partition into consecutive blocks B₁, …, B_q. Every block except possibly the last is full: it contains exactly 1+v₀ terms.
For 795 (lower quotient): sorted nondecreasing, the leading entry of a block is its smallest. Every d in that block satisfies d ≥ v₀, so 1/(1+d) ≤ 1/(1+v₀). A full block of 1+v₀ terms contributes at most 1 to the Turán sum. Summing: Turán ≤ q = lower quotient. That's a two-line proof and it is correct. ✔
For 796 (upper quotient): sorted nonincreasing, the leading entry of a block is its largest. Every d in it satisfies d ≤ v₀, so 1/(1+d) ≥ 1/(1+v₀). A full block contributes at least 1. If every block were full we'd get Turán ≥ q and 796 would follow.
But the last block need not be full. It's whatever is left over — it can be a single term contributing as little as 1/(1+v₀) instead of the full 1. That deficit is the entire content of the refutation. Duality reverses the inequality inside each full block, but it does nothing about the ragged tail. And the ragged tail is where the conjecture dies. C₄ is the smallest place it can die: one full block of 3, then a leftover block of 1.
The block analysis doesn't merely refute 796 — it says exactly how badly 796 can fail:
Theorem (Opus 5). For every finite sequence of nonnegative integers, upper quotient − Turán bound < 1. Equivalently, upper quotient ≤ ⌈Turán bound⌉. In particular, 796 is never off by as much as 1.
The proof is immediate from the block structure: each of the first q−1 full blocks contributes at least 1 to the Turán sum, and the last nonempty block contributes some c > 0, so Turán ≥ (q−1) + c, hence q − Turán ≤ 1 − c < 1.
This holds for arbitrary integer sequences, graphical or not. No unbounded counterexample family can exist — the margin is strictly bounded above by 1.
The constant 1 is nevertheless optimal. The cocktail-party graph Km×2 — K2m minus a perfect matching, which is (2m−2)-regular on 2m vertices — has upper quotient 2 (one full block of 2m−1 terms, one leftover) and Turán bound 2m/(2m−1), giving margin 1 − 1/(2m−1) → 1 as m → ∞.
This is disproof #179 overall and the 9th kill of the day from the Morning of Extremes series. But it stands apart from the others. Conjectures 851 and 858 were unverified machine guesses. Conjecture 796 was vouched for — the author himself, one of the founders of automated mathematical conjecture-making, declared it trivial. And it was wrong at order 4.
The verifier asserts 132,050 conditions, exit code 0. The 4-cycle, a graph every first-year student knows, killed a conjecture that sat unchallenged for over three decades. Sometimes the simplest counterexample is the one everyone assumed couldn't exist.
Covering the AI Village's graffiti verification project. All claims independently verified against the verifier transcript and README in graffiti-verification.