AFTD Auto-Formalizing Theoretical Domains

stc_reduction_gadget

def

The graph H_A obtained from Q by adding, for every pair i and every j < A, a new vertex w_{ij} joined to s_i and to t_i.

Statement

def stc_reduction_gadget {V : Type*} (Q : SimpleGraph V) {p : ℕ} (s t : Fin p → V) (A : ℕ) :
    SimpleGraph (Sum V (Fin p × Fin A))
Source
step towards weighted_spanning_tree_congestion_hardness_gap
Verified
05 Nov 2026
Axioms
none listed

Lean source view module on GitHub

/-- The reduction graph `H_A` on `V ⊕ (Fin p × Fin A)`: the edges of `Q` on the `V` part, plus, for each `(i,j)`, the two edges joining the auxiliary vertex `(i,j)` to `s i` and to `t i`. -/
def stc_reduction_gadget {V : Type*} (Q : SimpleGraph V) {p : ℕ} (s t : Fin p → V) (A : ℕ) :
    SimpleGraph (Sum V (Fin p × Fin A)) :=
  let H_adj : Sum V (Fin p × Fin A) → Sum V (Fin p × Fin A) → Prop := fun x y =>
    match x, y with
    | Sum.inl u, Sum.inl v => Q.Adj u v
    | Sum.inl u, Sum.inr (i, _) => u = s i ∨ u = t i
    | Sum.inr (i, _), Sum.inl u => u = s i ∨ u = t i
    | Sum.inr _, Sum.inr _ => False
  ⟨H_adj,
   ⟨fun x y => by
      rcases x with u | ⟨i, j⟩ <;> rcases y with v | ⟨i', j'⟩
      · exact fun h => h.symm
      · exact id
      · exact id
      · exact fun h => h.elim⟩,
   ⟨fun x => by
      rcases x with u | ⟨i, j⟩
      · exact Q.irrefl
      · exact fun h => h⟩⟩
See it in the graphDiscuss this resultChallenge it