graph_clique_partition_oriented_cross_degree_bound
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
- graph_125_exceptional_three_clique_cross_boundFor an oriented subdigraph of a graph on 125 vertices, suppose the vertices other than a distinguished vertex form three color classes…
- graph_125_three_clique_partition_oriented_cross_boundFor a graph on 125 vertices partitioned into three cliques, with at most 2583 graph edges, each part has at least seven vertices and every…
- graph_125_induced_clique_cross_boundIf the 124 vertices outside a distinguished vertex of a graph form three color classes that are cliques, then the number of crossing arcs…
- graph_125_three_cliques_except_vertex_boundsIf a graph on 125 vertices has at most 2583 edges and its vertices other than one distinguished vertex form three cliques, then at least…
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.
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.
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
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.
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_disjointhave 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
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.
uses
Finset.card_erase_of_memhave hcount (v : α) : (inside v).card = n (col v) - 1 := by apply Finset.card_erase_of_mem simp [S]
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.
uses
Finset.sum_fiberwise,Finset.sum_congr,Finset.mem_filter.mphave 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]
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$.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_comm,Finset.sum_congr,Ne.symmhave 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]
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.
uses
Finset.sum_le_sum,Finset.sum_add_distrib,G.sum_degrees_eq_twice_card_edgeshave 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
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.
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