Graph labelings assign integers to the vertices of a graph subject to arithmetic conditions on the edges; Gallian's dynamic survey (Electron. J. Combin., DS6) lists several thousand papers on them. A prime labeling asks for distinct labels with coprime labels on every edge. Its relaxation, the prime cordial labeling of Sundaram, Ponraj and Somasundaram (2005), only asks that the coprime and the non-coprime edges be balanced: their numbers may differ by at most one. Deciding which families are prime cordial is a standard question in the area. Paths are prime cordial exactly when , cycles exactly when , and the authors of the source paper have treated the generalized Petersen graphs (all except ) and flower snarks.
Knödel graphs were introduced by Knödel (1975) as the topology of a time-optimal gossiping scheme among nodes and were formally defined by Cohen, Fraigniaud and Gavoille (Discrete Math. 250 (2002), 41–62). With the hypercube and the recursive circulant graphs they are a standard family of interconnection networks. The paper this mission formalizes (Haque, Khanam and Shahriar, manuscript, 2026) settles prime cordiality for the cubic Knödel graphs .
All graphs are finite and simple. For a graph and a map , give each edge the label if and the label if , and let , be the numbers of edges with each label. The map is a prime cordial labeling if it is a bijection from onto and
is prime cordial (PrimeCordial G) if it has a prime cordial labeling (IsPrimeCordialLabeling G f).
For even and , the Knödel graph (knodel Δ n) has the vertices with and , and an edge from to for every and every . For the offsets are ; the graph is defined for even , is -regular and has edges.
The paper names the vertices by one index read modulo : and (vtx). Under this naming becomes the cyclic model (cyc n): the -cycle together with the chords . All labelings in the paper are functions of the index ; the basic one (labelF) is a permutation of each block of twelve consecutive values, defined by the residue of modulo .
Both directions are part of the statement: the positive clause for every and the exception .
The goal is milestones 2 and 5 together.
The theorem completes the classification of prime cordiality for the cubic Knödel graphs, adding to the list of families (paths, cycles, generalized Petersen graphs, flower snarks) whose prime cordiality is known exactly, with a single small exception. Its constructive half gives explicit labelings , one per residue class of modulo , which are reusable templates for other circulant-like cubic graphs built from a Hamiltonian cycle plus regular chords.
The paper verifies only Case 1 () and leaves the five other residue classes to the reader. Lemma 2.2 is stated without proof. A machine-checked proof therefore supplies the parts of the argument that are not written down, as well as the counting in Case 1. No formalization of prime cordial labelings or of Knödel graphs exists on the platform or in Mathlib.
The exception is a finite statement: has candidate bijections and edges. The paper's argument uses that the labels are coprime to every other label in , that these three vertices meet at least edges because the girth of is , and that edges cannot then split –. A brute-force enumeration is possible but large for kernel evaluation.
The positive half is uniform in , and that is where the work lies. For each residue class of modulo one must show that a specific labeling is a bijection onto and count, along the cycle edges and the chords, how many have coprime end labels. Inside a block of twelve the gcds are controlled by small differences (via Lemma 2.2), but the edges that wrap around from to and the chords near the end of the cycle cross block boundaries and depend on . These boundary edges are exactly where the labelings modify , and where a naive periodicity argument fails.
SimpleGraphs on finite types; edges are the undirected edges edgeFinset, each counted once. Labels are natural numbers, and a labeling is Set.BijOn f univ (Icc 1 |V|), so the labels are , never . The balance condition is computed in .Fin 2 × Fin (n / 2), with the paper's sides as the values . The definition is total in and ; every statement restricts to the paper's domain, Even n and 8 ≤ n for . For odd , Fin (n / 2) would give a graph on vertices, which is not ; the hypothesis Even n is therefore never dropped.Fin n with indices modulo . Its identification with is milestone 1, not an assumption.Useful reusable pieces include a general lemma on counting edges of a cycle-plus-chords graph by residue classes, and the Lemma 2.2 criterion in the form used here. Contributions of proofs for any of the six residue classes, as separate lemmas stating the explicit labeling and its counts, are welcome.
namespace KnodelPrimeCordial
/-- **Theorem 2.4** (Haque, Khanam, Shahriar, *Prime cordial labeling of Knödel graph*,
manuscript (2026), §2, p.6; abstract, p.1): "W(3, n) is prime cordial for all n except
W(3, 8)."
For every even `n ≥ 8` (the range on which `W_{3,n}` is defined, `3 ≤ ⌊log₂ n⌋`), the Knödel
graph `W_{3,n}` is prime cordial if and only if `n ≠ 8`.
**Formalization Note** "All n" is the definition's domain, `Even n ∧ 8 ≤ n`. The "except"
clause is part of the statement: `W_{3,8}` is not prime cordial. -/
theorem theorem_2_4_prime_cordial_iff (n : ℕ) (hn : Even n) (h8 : 8 ≤ n) :
PrimeCordial (knodel 3 n) ↔ n ≠ 8 := by sorry
end KnodelPrimeCordial
For every even (the range on which the Knödel graph is defined, since ),
That is, every with admits a bijection onto whose numbers of edges with coprime and with non-coprime end labels differ by at most one, and admits none. This is the paper's main result (" is prime cordial for all except "); both the positive clause and the exception are part of the statement.
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.