AFTD Auto-Formalizing Theoretical Domains

subdivided_doubled_complete_graph

def

For every natural number t, the 1-subdivision of the doubled complete multigraph on t vertices is the bipartite simple graph on Fin t ⊕ { p : Fin t × Fin t // p.1 ≠ p.2 } where each vertex (i, j) in the right part is adjacent to x_i and x_j in the left part.

Statement

def subdivided_doubled_complete_graph (t : ℕ) :
    SimpleGraph (Sum (Fin t) { p : Fin t × Fin t // p.1 ≠ p.2 })
Defined in
arXiv:2611.17022, Section 2
Verified
16 Nov 2026
Axioms
none listed

Read back from the Lean

Given a natural number $t$, subdivided_doubled_complete_graph t is the simple graph whose vertex type is the disjoint union (sum type) of $\operatorname{Fin} t$ and the subtype of pairs $(x, y) \in \operatorname{Fin} t \times \operatorname{Fin} t$ such that $x \ne y$, with adjacency defined by: - A vertex $\operatorname{Sum.inl}(i)$ (for $i \in \operatorname{Fin} t$) and a vertex $\operatorname{Sum.inr}(x, y)$ (for $(x, y) \in \operatorname{Fin} t \times \operatorname{Fin} t$ with $x \ne y$) are adjacent if and only if $i = x$ or $i = y$; - No two vertices in the left summand $\operatorname{Fin} t$ are adjacent; - No two vertices in the right summand are adjacent.

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

/-- The 1-subdivision of the doubled complete multigraph on t vertices, with parts X = Fin t and Y = {p : Fin t × Fin t // p.1 ≠ p.2}. -/
def subdivided_doubled_complete_graph (t : ℕ) :
    SimpleGraph (Sum (Fin t) { p : Fin t × Fin t // p.1 ≠ p.2 }) := {
  Adj := fun u v => match u, v with
    | Sum.inl i, Sum.inr ⟨(x, y), _⟩ => i = x ∨ i = y
    | Sum.inr ⟨(x, y), _⟩, Sum.inl i => i = x ∨ i = y
    | _, _ => False
  symm := ⟨by rintro (i | ⟨⟨x, y⟩, hne⟩) (j | ⟨⟨x', y'⟩, hne'⟩) h <;> simp_all⟩
  loopless := ⟨by rintro (i | ⟨⟨x, y⟩, hne⟩) <;> simp⟩
}
See it in the graphDiscuss this resultChallenge it