AFTD Auto-Formalizing Theoretical Domains

gt_adj

def

The adjacency relation gt_adj t on GtVertex t: vertices u and v are adjacent if and only if (u is in A and v is in B, or vice versa), (u is in B and v is in C, or vice versa), (u is in C and v is in D, or vice versa), (one is in {A, B, C, D} and the other in {P, Q, R}), (u is in P and v is in Q, or vice versa), (u is in P and v is in R, or vice versa), (u is in Q and v is in R, or vice versa), or both are distinct vertices R i and R j with i ≠ j.

Statement

def gt_adj (t : ℕ) : GtVertex t → GtVertex t → Prop
Defined in
arXiv:2611.11352 Definition 1, Definition 2
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • GtVertexThe vertex set of the graph G_t partitioned into blocks A (size 3), B (size 2), C (size 2), D (size 3), P (size t), Q (size t), and R…
Used by 3
  • gt_total_forcing_poly_eqFor every integer t ≥ 24, the total forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
  • gt_connected_forcing_poly_eqFor every integer t ≥ 24, the connected forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
  • gt_graphThe simple graph gt_graph t on vertex type GtVertex t, defined as SimpleGraph.fromRel (gt_adj t).

Read back from the Lean

Given a natural number t, gt_adj t is a binary relation on GtVertex t (defining an undirected graph adjacency relation) that holds between two vertices u and v if and only if one of the following symmetric cases holds: 1. One vertex is of constructor A and the other is of constructor B. 2. One vertex is of constructor B and the other is of constructor C. 3. One vertex is of constructor C and the other is of constructor D. 4. One vertex is in {A, B, C, D} and the other is in {P, Q, R} (a complete bipartite connection between {A, B, C, D} and {P, Q, R}). 5. One vertex is of constructor P and the other is of constructor Q. 6. One vertex is of constructor P and the other is of constructor R. 7. One vertex is of constructor Q and the other is of constructor R. 8. Both vertices are of constructor R, say R i and R j, with i ≠ j. In all other cases (including self-loops, pairs within A, B, C, D, P, or Q, and pairs between A and C, A and D, or B and D), the relation is False.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Adjacency relation of G_t. -/
def gt_adj (t : ℕ) : GtVertex t → GtVertex t → Prop := fun u v => match u, v with
  | .A _, .B _ => True
  | .B _, .A _ => True
  | .B _, .C _ => True
  | .C _, .B _ => True
  | .C _, .D _ => True
  | .D _, .C _ => True
  | .A _, .P _ => True | .P _, .A _ => True
  | .A _, .Q _ => True | .Q _, .A _ => True
  | .A _, .R _ => True | .R _, .A _ => True
  | .B _, .P _ => True | .P _, .B _ => True
  | .B _, .Q _ => True | .Q _, .B _ => True
  | .B _, .R _ => True | .R _, .B _ => True
  | .C _, .P _ => True | .P _, .C _ => True
  | .C _, .Q _ => True | .Q _, .C _ => True
  | .C _, .R _ => True | .R _, .C _ => True
  | .D _, .P _ => True | .P _, .D _ => True
  | .D _, .Q _ => True | .Q _, .D _ => True
  | .D _, .R _ => True | .R _, .D _ => True
  | .P _, .Q _ => True | .Q _, .P _ => True
  | .P _, .R _ => True | .R _, .P _ => True
  | .Q _, .R _ => True | .R _, .Q _ => True
  | .R i, .R j => i ≠ j
  | _, _ => False
See it in the graphDiscuss this resultChallenge it