digraph_linear_arc_dominated_balanced
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
- digraph_clean_center_indegree_ge_outdegreeIn a finite loopless arc-dominated digraph, a vertex with a clean out-neighborhood has indegree at least its outdegree.
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.
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$.
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
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.
uses
digraph_clean_center_indegree_ge_outdegreehave 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
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.
uses
Finset.sum_congr,Finset.sum_ite,Finset.sum_commhave 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]
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)|$.
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
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.
uses
Finset.sum_lt_sum,Finset.mem_univhave 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`.
- Linear integer arithmetic is handled automatically by `omega` to infer strict inequality from non-strict inequality and disequality, and to deduce a contradiction from $A = B$ and $A < B$.
- The simplification steps in the double-counting argument rewrite set cardinalities to sums of indicator functions ($if\ D.Adj\ v\ w\ then\ 1\ else\ 0$).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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