Lemma 2.1 — is not prime cordial
ProvedKnodelPrimeCordial.lemma_2_1graph-labelingknodel-graphp2o-gran-per-chapterp2o-plan-paperp2o-v1prime-cordial
The Knödel graph (eight vertices, twelve edges, -regular) is not prime cordial: for every bijection from its vertex set onto , the numbers of edges with and with differ by at least .
This is the single exception in the paper's main theorem.
Differences from the source:
- encoding: vertex (i, j) with i = 1, 2 → Fin 2 × Fin 4 with sides 1, 2 as 0, 1; reason: Lean convention; same graph
- encoding: bijection f from V to {1, …, |V|} → f : V → ℕ with Set.BijOn f univ (Icc 1 |V|); reason: Lean convention; same labelings
Preamble
import Mathlib import Definitions.Def_KnodelPrimeCordial_PrimeCordial import Definitions.Def_KnodelPrimeCordial_knodel
Formal statement
namespace KnodelPrimeCordial
/-- **Lemma 2.1** (Haque, Khanam, Shahriar, *Prime cordial labeling of Knödel graph*,
manuscript (2026), §2, p.3): "W(3, 8) is not prime cordial."
The Knödel graph `W_{3,8}` (8 vertices, 12 edges) has no prime cordial labeling. -/
theorem lemma_2_1 : ¬ PrimeCordial (knodel 3 8) := by sorry
end KnodelPrimeCordial
Source
Haque, Khanam, Shahriar, Prime cordial labeling of Knödel graph, manuscript (2026) (held version, sha256 366502170d8d7c65ccc2fcc6f5373dac872d6efdc838ba9e671eb578e4c08c60), Lemma 2.1, p.3 (PDF p.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.