AFTD Auto-Formalizing Theoretical Domains

graph_clique_partition_oriented_cross_degree_bound

theoremverified

If the color classes of a finite graph are cliques and an oriented digraph is a spanning subgraph, then twice its number of crossing arcs plus the sum of the products of each color-class size and its predecessor is at most twice the number of graph edges.

Statement

theorem graph_clique_partition_oriented_cross_degree_bound
    (α κ : Type) [Fintype α] [DecidableEq α] [Fintype κ] [DecidableEq κ]
    (G : SimpleGraph α) [DecidableRel G.Adj]
    (D : Digraph α) [DecidableRel D.Adj] (col : α → κ)
    (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v)
    (hsub : ∀ u v, D.Adj u v → G.Adj u v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) :
    (∑ i : κ, (Finset.univ.filter fun v => col v = i).card *
      ((Finset.univ.filter fun v => col v = i).card - 1)) +
    2 * (∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤
      2 * G.edgeFinset.card
Source
Degree-counting bridge for OP-110 and the exceptional-vertex reductions.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 4

The proof, explained

The proof establishes a local degree inequality for each vertex and sums it over the entire graph. For each vertex $v$, its neighbors within the same color clique, its outgoing crossing neighbors in $D$, and its incoming crossing neighbors in $D$ are mutually disjoint and all adjacent to $v$ in $G$, so their sizes sum to at most $\deg_G(v)$. Summing over all vertices, the monochromatic terms total $\sum_i n_i (n_i - 1)$, the incoming and outgoing crossing arc totals are equal by double counting, and the degrees sum to $2 |E(G)|$ by Euler's handshaking lemma.

  1. Notation is defined for color classes, their sizes, monochromatic neighbors, and crossing in- and out-neighbors.

    Enable classical reasoning and define shorthands: $S_i$ is the color class of vertices of color $i$, $n_i = |S_i|$, and for each vertex $v$, $\text{inside}(v) = S_{\text{col}(v)} \setminus \{v\}$ is the set of other vertices of the same color, $\text{out}(v)$ is the set of out-neighbors of $v$ in $D$ with a different color, and $\text{inc}(v)$ is the set of in-neighbors of $v$ in $D$ with a different color.

    lines 15–22

      classical
      let S : κ → Finset (α) := fun i => Finset.univ.filter fun v => col v = i
      let n : κ → ℕ := fun i => (S i).card
      let inside : α → Finset (α) := fun v => (S (col v)).erase v
      let out : α → Finset (α) := fun v =>
        Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w
      let inc : α → Finset (α) := fun v =>
        Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj w v
  2. For every vertex $v$, the sizes of its monochromatic neighbors and crossing neighbors sum to at most its degree: $|\text{inside}(v)| + |\text{out}(v)| + |\text{inc}(v)| \le \deg_G(v)$.

    The three sets are pairwise disjoint: $\text{inside}(v)$ has vertices of color $\text{col}(v)$ while $\text{out}(v)$ and $\text{inc}(v)$ have vertices of different colors, and $\text{out}(v)$ and $\text{inc}(v)$ are disjoint because $D$ is oriented (hypothesis hori forbids 2-cycles). Furthermore, all three sets are contained in the neighborhood of $v$ in $G$: $\text{inside}(v)$ connects to $v$ because each color class is a clique (hclique), and $\text{out}(v)$ and $\text{inc}(v)$ connect to $v$ because $D$ is a subgraph of $G$ (hsub) and adjacency in $G$ is symmetric. Applying the disjoint union cardinality formula to this inclusion gives the bound.

    lines 23–56

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp, Finset.mem_erase.mp, Finset.disjoint_union_right.mpr, SimpleGraph.mem_neighborFinset, Finset.mem_union.mp, Finset.card_le_card, Finset.card_union_of_disjoint

      have hlocal (v : α) : (inside v).card + (out v).card + (inc v).card ≤ G.degree v := by
        have hab : Disjoint (inside v) (out v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2
          have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1
          exact h2 h1
        have hac : Disjoint (inside v) (inc v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2
          have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1
          exact h2 h1
        have hbc : Disjoint (out v) (inc v) := by
          apply Finset.disjoint_left.mpr
          intro w hw1 hw2
          have h1 : D.Adj v w := (Finset.mem_filter.mp hw1).2.2
          have h2 : D.Adj w v := (Finset.mem_filter.mp hw2).2.2
          exact hori v w h1 h2
        have hall : Disjoint (inside v) (out v ∪ inc v) := Finset.disjoint_union_right.mpr ⟨hab, hac⟩
        have hsubset : inside v ∪ (out v ∪ inc v) ⊆ G.neighborFinset v := by
          intro w hw
          simp only [SimpleGraph.mem_neighborFinset]
          rcases Finset.mem_union.mp hw with ha | ha
          · have hw' := Finset.mem_erase.mp ha
            have hc : col w = col v := (Finset.mem_filter.mp hw'.2).2
            exact hclique v w hc.symm hw'.1.symm
          · rcases Finset.mem_union.mp ha with hb | hc
            · exact hsub v w (Finset.mem_filter.mp hb).2.2
            · exact (hsub w v (Finset.mem_filter.mp hc).2.2).symm
        have hh := Finset.card_le_card hsubset
        rw [Finset.card_union_of_disjoint hall, Finset.card_union_of_disjoint hbc] at hh
        change _ ≤ G.degree v at hh
        omega
  3. For every vertex $v$, the number of other vertices in its color class is $|\text{inside}(v)| = n(\text{col}(v)) - 1$.

    Because $v$ belongs to its own color class $S_{\text{col}(v)}$, erasing $v$ from this set of size $n(\text{col}(v))$ decreases its cardinality by 1 using Finset.card_erase_of_mem.

    lines 57–59

    uses Finset.card_erase_of_mem

      have hcount (v : α) : (inside v).card = n (col v) - 1 := by
        apply Finset.card_erase_of_mem
        simp [S]
  4. Summing the monochromatic neighborhood sizes over all vertices gives $\sum_{i \in \kappa} n_i (n_i - 1)$.

    Substitute $|\text{inside}(v)| = n(\text{col}(v)) - 1$ into the sum over all vertices. Grouping the vertices by fibers of the coloring function via Finset.sum_fiberwise, each fiber of color $i$ has $n_i$ vertices with the constant summand $n_i - 1$, producing $n_i(n_i - 1)$ for each color class.

    lines 60–71

    uses Finset.sum_fiberwise, Finset.sum_congr, Finset.mem_filter.mp

      have hinside : (∑ v : α, (inside v).card) = ∑ i : κ, n i * (n i - 1) := by
        simp_rw [hcount]
        rw [← Finset.sum_fiberwise Finset.univ col]
        apply Finset.sum_congr rfl
        intro i hi
        calc
          (∑ v ∈ Finset.univ.filter (fun v => col v = i), (n (col v) - 1)) =
              ∑ _v ∈ Finset.univ.filter (fun v => col v = i), (n i - 1) := by
                apply Finset.sum_congr rfl
                intro v hv
                rw [(Finset.mem_filter.mp hv).2]
          _ = n i * (n i - 1) := by simp [n,S]
  5. The total number of crossing out-arcs equals the total number of crossing in-arcs: $\sum_{v \in \alpha} |\text{out}(v)| = \sum_{v \in \alpha} |\text{inc}(v)|$.

    Express the sizes of $\text{out}(v)$ and $\text{inc}(v)$ as sums of indicator 1s over pairs $(v, w)$ satisfying the crossing arc condition. Swapping the order of summation with Finset.sum_comm interchanges the source and target roles, showing that both double sums count the total number of crossing directed arcs in $D$.

    lines 72–79

    uses Finset.card_eq_sum_ones, Finset.sum_filter, Finset.sum_comm, Finset.sum_congr, Ne.symm

      have hcross : (∑ v : α, (out v).card) = ∑ v : α, (inc v).card := by
        simp only [out, inc, Finset.card_eq_sum_ones, Finset.sum_filter]
        rw [Finset.sum_comm]
        apply Finset.sum_congr rfl
        intro v hv
        apply Finset.sum_congr rfl
        intro w hw
        by_cases h : col w = col v <;> by_cases hd : D.Adj v w <;> simp [h, Ne.symm, hd]
  6. Twice the number of crossing arcs plus the sum of $n_i(n_i - 1)$ is at most twice the number of edges in $G$.

    Sum the local degree inequality $|\text{inside}(v)| + |\text{out}(v)| + |\text{inc}(v)| \le \deg_G(v)$ over all vertices $v$ using Finset.sum_le_sum and distribute the sums. Substitute the monochromatic sum $\sum_i n_i (n_i - 1)$, replace the in-arc sum with the out-arc sum to get $2 \sum_v |\text{out}(v)|$, and replace the sum of degrees with $2 |E(G)|$ by Euler's handshaking lemma G.sum_degrees_eq_twice_card_edges. Linear arithmetic closes the goal.

    lines 80–84

    uses Finset.sum_le_sum, Finset.sum_add_distrib, G.sum_degrees_eq_twice_card_edges

      have hh := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset α)) => hlocal v)
      simp only [Finset.sum_add_distrib] at hh
      rw [hinside, ← hcross, G.sum_degrees_eq_twice_card_edges] at hh
      change (∑ i : κ, n i * (n i - 1)) + 2 * (∑ v : α, (out v).card) ≤ _
      omega
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp
An element in a filtered finite set belongs to the original set and satisfies the filter predicate.
Finset.mem_erase.mp
An element of a finite set with an element erased is distinct from the erased element and belongs to the original set.
Finset.disjoint_union_right.mpr
If a finite set is disjoint from each of two other finite sets, it is disjoint from their union.
SimpleGraph.mem_neighborFinset
A vertex belongs to the neighbor finset of a vertex if and only if the two vertices are adjacent in the simple graph.
Finset.mem_union.mp
An element in the union of two finite sets belongs to the first or to the second.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_erase_of_mem
Erasing an element from a finite set containing it reduces the cardinality by 1.
Finset.sum_fiberwise
A sum over a finite set can be grouped into a double sum by the fibers of a function into a finite type.
Finset.sum_congr
Sums of equal functions over equal finite sets are equal.
Finset.card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all its elements.
Finset.sum_filter
The sum of a function over a filtered finite set equals the sum over the base set of the indicator of the condition times the function.
Finset.sum_comm
The order of summation in a double finite sum can be exchanged.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.sum_le_sum
If a termwise inequality holds between functions on a finite set, the corresponding sum inequality holds.
Finset.sum_add_distrib
The sum of a termwise sum of two functions on a finite set is the sum of the two sums.
G.sum_degrees_eq_twice_card_edges
In any finite simple graph, the sum of degrees over all vertices equals twice the number of edges.

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

set_option maxHeartbeats 2000000set_option maxRecDepth 4096theorem graph_clique_partition_oriented_cross_degree_bound    (α κ : Type) [Fintype α] [DecidableEq α] [Fintype κ] [DecidableEq κ]    (G : SimpleGraph α) [DecidableRel G.Adj]    (D : Digraph α) [DecidableRel D.Adj] (col : α → κ)    (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v)    (hsub : ∀ u v, D.Adj u v → G.Adj u v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) :    (∑ i : κ, (Finset.univ.filter fun v => col v = i).card *      ((Finset.univ.filter fun v => col v = i).card - 1)) +    2 * (∑ v : α, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤      2 * G.edgeFinset.card := by  classical  let S : κ → Finset (α) := fun i => Finset.univ.filter fun v => col v = i  let n : κ → ℕ := fun i => (S i).card  let inside : α → Finset (α) := fun v => (S (col v)).erase v  let out : α → Finset (α) := fun v =>    Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w  let inc : α → Finset (α) := fun v =>    Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj w v  have hlocal (v : α) : (inside v).card + (out v).card + (inc v).card ≤ G.degree v := by    have hab : Disjoint (inside v) (out v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2      have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1      exact h2 h1    have hac : Disjoint (inside v) (inc v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : col w = col v := (Finset.mem_filter.mp (Finset.mem_erase.mp hw1).2).2      have h2 : col w ≠ col v := (Finset.mem_filter.mp hw2).2.1      exact h2 h1    have hbc : Disjoint (out v) (inc v) := by      apply Finset.disjoint_left.mpr      intro w hw1 hw2      have h1 : D.Adj v w := (Finset.mem_filter.mp hw1).2.2      have h2 : D.Adj w v := (Finset.mem_filter.mp hw2).2.2      exact hori v w h1 h2    have hall : Disjoint (inside v) (out v ∪ inc v) := Finset.disjoint_union_right.mpr ⟨hab, hac⟩    have hsubset : inside v ∪ (out v ∪ inc v) ⊆ G.neighborFinset v := by      intro w hw      simp only [SimpleGraph.mem_neighborFinset]      rcases Finset.mem_union.mp hw with ha | ha      · have hw' := Finset.mem_erase.mp ha        have hc : col w = col v := (Finset.mem_filter.mp hw'.2).2        exact hclique v w hc.symm hw'.1.symm      · rcases Finset.mem_union.mp ha with hb | hc        · exact hsub v w (Finset.mem_filter.mp hb).2.2        · exact (hsub w v (Finset.mem_filter.mp hc).2.2).symm    have hh := Finset.card_le_card hsubset    rw [Finset.card_union_of_disjoint hall, Finset.card_union_of_disjoint hbc] at hh    change _ ≤ G.degree v at hh    omega  have hcount (v : α) : (inside v).card = n (col v) - 1 := by    apply Finset.card_erase_of_mem    simp [S]  have hinside : (∑ v : α, (inside v).card) = ∑ i : κ, n i * (n i - 1) := by    simp_rw [hcount]    rw [← Finset.sum_fiberwise Finset.univ col]    apply Finset.sum_congr rfl    intro i hi    calc      (∑ v ∈ Finset.univ.filter (fun v => col v = i), (n (col v) - 1)) =          ∑ _v ∈ Finset.univ.filter (fun v => col v = i), (n i - 1) := by            apply Finset.sum_congr rfl            intro v hv            rw [(Finset.mem_filter.mp hv).2]      _ = n i * (n i - 1) := by simp [n,S]  have hcross : (∑ v : α, (out v).card) = ∑ v : α, (inc v).card := by    simp only [out, inc, Finset.card_eq_sum_ones, Finset.sum_filter]    rw [Finset.sum_comm]    apply Finset.sum_congr rfl    intro v hv    apply Finset.sum_congr rfl    intro w hw    by_cases h : col w = col v <;> by_cases hd : D.Adj v w <;> simp [h, Ne.symm, hd]  have hh := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset α)) => hlocal v)  simp only [Finset.sum_add_distrib] at hh  rw [hinside, ← hcross, G.sum_degrees_eq_twice_card_edges] at hh  change (∑ i : κ, n i * (n i - 1)) + 2 * (∑ v : α, (out v).card) ≤ _  omega
See it in the graphDiscuss this resultChallenge it