Graffiti.pc Conjecture 318

What Lean checks

The all-order theorem uses actual graph distances and undirected complement-edge counts. Every total dominating set contains an adjacent total dominating pair; every minimal set has size two. The stated five-vertex graph proves sharpness of a one-unit relaxation.

Result and proof credited to @JesterInABarrel. This is an external contribution.

Collection · Catalogue · Verification · Lean status

Result credit: @JesterInABarrel on X. This result and proof were publicly shared by that account on November 18, 2026, through a ChatGPT conversation, and included here with permission. This is an external contribution. Neither Cinna Davis nor the repository's AI collaborator is credited with discovering or authoring this result.

Result

Graffiti.pc Conjecture 318 (DeLaViña, 2007) is true. In fact, if a finite simple connected graph GG on at least two vertices satisfies

maxv∈V(G)disteven(v)≥|E(G¯)|,\max_{v\in V(G)}\mathop{\mathrm{dist}}_{even}(v)\ \geq\ |E(\overline G)|,

then every total dominating set contains a total dominating pair. Consequently every inclusion-minimal total dominating set has exactly two adjacent vertices, and GG is well total dominated.

The original conjecture was listed as open in the November 5, 2026 catalogue.

Proof, source and credit

Cite @JesterInABarrel when referring to this result. This repository maintains an independently checked presentation, not a separate discovery claim.

Verification

From the repository root:

python3 results/graffiti-pc-318/verify.py

The standard-library verifier checks 419,235 labeled graphs, including every graph of order 2–7 that could meet the hypothesis. All 7,337 qualifying graphs satisfy the stronger conclusion. It also checks a five-vertex sharpness example. The all-order proof does not rely on finite enumeration.

Formalization

The all-order Lean theorem and the five-vertex sharpness example have passed local source compilation, a transitive axiom audit, and independent kernel replay. The hosted candidate checks also passed. All three modules are registered in the accepted package, its required endpoint audit, and its kernel replay list. See the exact statements and local receipts, the candidate checks, and the Lean status report. The result remains unrefereed and lacks independent peer review.