subdivided_doubled_complete_graph
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⟩ }