AFTD Auto-Formalizing Theoretical Domains

song_edge_graph

def

The alternating graph H = (V_{2k-1}, M ∪ N) on the (2k)x(2k) grid vertices, whose edges are the selected diagonals together with the auxiliary matching N of the blocks.

Statement

noncomputable def song_edge_graph (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : SimpleGraph (Fin (2 * k) × Fin (2 * k))
Source
step towards admissible_diagonal_selection_isometric_path_cover
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • song_aux_matchingThe auxiliary perfect matching N of the blocks: in a block that already carries a diagonal of M (ad or bc), take the two horizontal edges…

Lean source view module on GitHub

/-- Alternating graph H = (V_{2k-1}, M ∪ N) whose edges are the admissible diagonals together with the auxiliary matching. -/
noncomputable def song_edge_graph (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : SimpleGraph (Fin (2 * k) × Fin (2 * k)) := SimpleGraph.fromEdgeSet ((M ∪ song_aux_matching k M : Finset _) : Set _)
See it in the graphDiscuss this resultChallenge it