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 _)