AFTD Auto-Formalizing Theoretical Domains

digraph_linear_arc_dominated_balanced

theoremverified

Every finite loopless linear arc-dominated digraph is balanced, without an outregularity assumption.

Statement

theorem digraph_linear_arc_dominated_balanced
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v)
    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)
    (hlinear : ∀ u v, u ≠ v → ∀ a b,
      D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) :
    ∀ v, (Finset.univ.filter fun w => D.Adj v w).card =
      (Finset.univ.filter fun w => D.Adj w v).card
Source
General zero-overlap structure for OP-110; exhaustive checks through order five in experiment 12675.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof establishes that every vertex is balanced by combining a local degree inequality with double counting. Linearity ensures that every vertex is a clean center, which implies that out-degree is at most in-degree everywhere ($\deg^+(v) \le \deg^-(v)$). Summing over all vertices and exchanging summation order shows that total out-degree equals total in-degree. Consequently, if any vertex had strictly smaller out-degree than in-degree, the total out-degree would be strictly less than the total in-degree, a contradiction.

  1. Introduce notation for the out-neighborhood and in-neighborhood of each vertex.

    We activate classical logic and introduce local definitions: `outs v` is the set of out-neighbors $\{w \mid D.Adj\ v\ w\}$ and `ins v` is the set of in-neighbors $\{w \mid D.Adj\ w\ v\}$ of a vertex $v$.

    lines 9–11

      classical
      let outs : α → Finset α := fun v => Finset.univ.filter fun w => D.Adj v w
      let ins : α → Finset α := fun v => Finset.univ.filter fun w => D.Adj w v
  2. For every vertex $v$, the out-degree is at most the in-degree: $|outs(v)| \le |ins(v)|$.

    We apply the lemma `digraph_clean_center_indegree_ge_outdegree` at $v$. The lemma requires showing that $v$ is a clean center: if $a \neq b$ are distinct out-neighbors of $v$ ($v \to a$ and $v \to b$), any vertex $p$ with arcs to both $a$ and $b$ must be $v$. This requirement is met directly by the linearity hypothesis `hlinear`, which states that two distinct vertices cannot share more than one in-neighbor.

    lines 12–16

    uses digraph_clean_center_indegree_ge_outdegree

      have hle : ∀ v, (outs v).card ≤ (ins v).card := by
        intro v
        apply digraph_clean_center_indegree_ge_outdegree α D hloop hdom v
        intro a b hab hva hvb p hpa hpb
        exact hlinear a b hab p v hpa hpb hva hvb
  3. The sum of all out-degrees equals the sum of all in-degrees: $\sum_{v} |outs(v)| = \sum_{v} |ins(v)|$.

    By double counting the arcs of the digraph, each out-degree is expressed as the sum of edge indicators $if\ D.Adj\ v\ w\ then\ 1\ else\ 0$ using `Finset.sum_congr` and `Finset.sum_ite`. Swapping the order of summation using `Finset.sum_comm` transforms the sum of out-degrees into the sum of in-degrees.

    lines 17–27

    uses Finset.sum_congr, Finset.sum_ite, Finset.sum_comm

      have hsum : (∑ v : α, (outs v).card) = ∑ v : α, (ins v).card := by
        calc
          (∑ v : α, (outs v).card) = ∑ v : α, ∑ w : α, if D.Adj v w then 1 else 0 := by
            apply Finset.sum_congr rfl
            intro v _
            simp [outs, Finset.sum_ite]
          _ = ∑ w : α, ∑ v : α, if D.Adj v w then 1 else 0 := Finset.sum_comm
          _ = ∑ w : α, (ins w).card := by
            apply Finset.sum_congr rfl
            intro w _
            simp [ins, Finset.sum_ite]
  4. If $|outs(v)| \ne |ins(v)|$ for some vertex $v$, then $|outs(v)| < |ins(v)|$.

    To prove $|outs(v)| = |ins(v)|$ for an arbitrary vertex $v$, assume for contradiction that $|outs(v)| \ne |ins(v)|$. Since we already proved $|outs(v)| \le |ins(v)|$, linear integer arithmetic (`omega`) deduces that the inequality is strict: $|outs(v)| < |ins(v)|$.

    lines 28–33

      intro v
      by_contra hne
      have hlt : (outs v).card < (ins v).card := by
        have hv := hle v
        change (outs v).card ≠ (ins v).card at hne
        omega
  5. The strict inequality at $v$ contradicts the equality of total sums, completing the proof.

    Because $|outs(w)| \le |ins(w)|$ for all $w$ and $|outs(v)| < |ins(v)|$ at vertex $v$ (with $v \in Finset.univ$ by `Finset.mem_univ`), `Finset.sum_lt_sum` implies that the total sum of out-degrees is strictly less than the total sum of in-degrees. This contradicts the handshaking identity $\sum outs = \sum ins$, and `omega` derives False to conclude the proof.

    lines 34–39

    uses Finset.sum_lt_sum, Finset.mem_univ

      have hsumlt : (∑ v : α, (outs v).card) < ∑ v : α, (ins v).card := by
        apply Finset.sum_lt_sum
        · intro w _
          exact hle w
        · exact ⟨v, Finset.mem_univ _, hlt⟩
      omega
digraph_clean_center_indegree_ge_outdegree
In a finite loopless arc-dominated digraph, if a vertex $v$ is a clean center (meaning no two distinct out-neighbors of $v$ have another common in-neighbor), then the out-degree of $v$ is at most its in-degree.
Finset.sum_congr
If two finite sets are equal and their summands agree on every element, their sums are equal.
Finset.sum_ite
The sum of an indicator/conditional splits into the sum over elements satisfying the condition and the sum over those that do not.
Finset.sum_comm
In a double sum over two finite sets, the order of summation can be exchanged.
Finset.sum_lt_sum
If $f(i) \le g(i)$ for all elements of a finite set and $f(i) < g(i)$ for at least one element, then $\sum f < \sum g$.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem digraph_linear_arc_dominated_balanced    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (hloop : ∀ v, ¬ D.Adj v v)    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)    (hlinear : ∀ u v, u ≠ v → ∀ a b,      D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) :    ∀ v, (Finset.univ.filter fun w => D.Adj v w).card =      (Finset.univ.filter fun w => D.Adj w v).card := by  classical  let outs : α → Finset α := fun v => Finset.univ.filter fun w => D.Adj v w  let ins : α → Finset α := fun v => Finset.univ.filter fun w => D.Adj w v  have hle : ∀ v, (outs v).card ≤ (ins v).card := by    intro v    apply digraph_clean_center_indegree_ge_outdegree α D hloop hdom v    intro a b hab hva hvb p hpa hpb    exact hlinear a b hab p v hpa hpb hva hvb  have hsum : (∑ v : α, (outs v).card) = ∑ v : α, (ins v).card := by    calc      (∑ v : α, (outs v).card) = ∑ v : α, ∑ w : α, if D.Adj v w then 1 else 0 := by        apply Finset.sum_congr rfl        intro v _        simp [outs, Finset.sum_ite]      _ = ∑ w : α, ∑ v : α, if D.Adj v w then 1 else 0 := Finset.sum_comm      _ = ∑ w : α, (ins w).card := by        apply Finset.sum_congr rfl        intro w _        simp [ins, Finset.sum_ite]  intro v  by_contra hne  have hlt : (outs v).card < (ins v).card := by    have hv := hle v    change (outs v).card ≠ (ins v).card at hne    omega  have hsumlt : (∑ v : α, (outs v).card) < ∑ v : α, (ins v).card := by    apply Finset.sum_lt_sum    · intro w _      exact hle w    · exact ⟨v, Finset.mem_univ _, hlt⟩  omega
See it in the graphDiscuss this resultChallenge it