simple_graph_exists_edge_tail_capacity
Every finite simple graph of maximum degree at least two admits an assignment of each edge to one of its endpoints, with at most maximum-degree-minus-one edges assigned to any vertex.
Statement
theorem simple_graph_exists_edge_tail_capacity {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : 2 ≤ G.maxDegree) : ∃ f : G.edgeSet → V, (∀ e : G.edgeSet, f e ∈ (e : Sym2 V)) ∧ ∀ v, (Finset.univ.filter (fun e => f e = v)).card ≤ G.maxDegree - 1
- Source
- Helper for OP-494 in arXiv:2610.30174, following the additive-list coloring argument of arXiv:2302.02190v3, Corollary 5.3. Apply the two-incidence capacity lemma to the edge subtype and use the incidence-finset degree bound.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finite_two_incidence_capacity_assignmentA finite incidence relation with two endpoints for every edge and at most d incident edges at every vertex, d at least two, admits an…
- Used by 1
- op_494_additive_chromatic_bipartite_maxDegreeLet G be a finite connected bipartite simple graph with maximum degree at least 2. Then there exists a vertex labeling f : V → ℕ such that…
The proof, explained
The proof reduces the problem to a general combinatorial assignment lemma, finite_two_incidence_capacity_assignment, which guarantees that whenever every edge has 2 endpoints and every vertex is incident to at most d edges (with d ≥ 2), edges can be assigned to incident vertices such that each vertex receives at most d - 1 edges. Applying this with d = G.maxDegree leaves two conditions to check: each edge has two endpoints, and each vertex has degree at most G.maxDegree. The first holds because simple graphs have no self-loops, and the second holds because the number of incident edges equals the vertex degree, which is bounded by the maximum degree.
The problem reduces to verifying that every edge has two endpoints and every vertex is incident to at most G.maxDegree edges.
Assuming classical logic, we apply the general assignment theorem finite_two_incidence_capacity_assignment to the incidence relation v ∈ e with capacity bound d = G.maxDegree. Since 2 ≤ G.maxDegree by assumption hd, this yields the desired edge assignment f once we show two facts: each edge contains exactly two vertices, and each vertex belongs to at most G.maxDegree edges.
uses
finite_two_incidence_capacity_assignmentclassical apply finite_two_incidence_capacity_assignment (fun (e : G.edgeSet) v => v ∈ (e : Sym2 V)) G.maxDegree hd
Every edge contains exactly two vertices.
For any edge e, the set of incident vertices {v | v ∈ e} is shown to equal the finset of endpoints (e : Sym2 V).toFinset. Because G is a simple graph, e cannot be a self-loop (G.not_isDiag_of_mem_edgeSet), so Sym2.card_toFinset_of_not_isDiag concludes that this finset has cardinality 2.
uses
Sym2.card_toFinset_of_not_isDiag,G.not_isDiag_of_mem_edgeSet· intro e have h : Finset.univ.filter (fun v => v ∈ (e : Sym2 V)) = (e : Sym2 V).toFinset := by ext v simp rw [h] exact Sym2.card_toFinset_of_not_isDiag _ (G.not_isDiag_of_mem_edgeSet e.property)
Every vertex is incident to at most G.maxDegree edges.
For any vertex v, we bound the number of incident edges by a chain of three steps. First, the coercion from the edge subtype G.edgeSet to Sym2 V is injective (Subtype.ext) and maps incident edges into G.incidenceFinset v (via G.mem_incidenceFinset, G.edge_mem_incidenceSet_iff, and Finset.mem_filter.mp), so Finset.card_le_card_of_injOn bounds the count by the size of the incidence finset. Second, this size equals the degree of v by G.card_incidenceFinset_eq_degree. Third, the degree of v is at most G.maxDegree by G.degree_le_maxDegree.
uses
Finset.card_le_card_of_injOn,G.mem_incidenceFinset,G.edge_mem_incidenceSet_iff,Finset.mem_filter.mp,Subtype.ext,G.card_incidenceFinset_eq_degree,G.degree_le_maxDegree· intro v calc (Finset.univ.filter (fun e : G.edgeSet => v ∈ (e : Sym2 V))).card ≤ (G.incidenceFinset v).card := by apply Finset.card_le_card_of_injOn (fun e : G.edgeSet => (e : Sym2 V)) · intro e he change (e : Sym2 V) ∈ G.incidenceFinset v rw [G.mem_incidenceFinset, G.edge_mem_incidenceSet_iff] exact (Finset.mem_filter.mp he).2 · intro e _ e' _ he exact Subtype.ext he _ = G.degree v := G.card_incidenceFinset_eq_degree v _ ≤ G.maxDegree := G.degree_le_maxDegree v
finite_two_incidence_capacity_assignment- In a bipartite incidence system between finite sets where each left element is incident to 2 right elements and each right element is incident to at most d left elements (with d ≥ 2), there exists an assignment of each left element to an incident right element such that each right element receives at most d - 1 elements.
Sym2.card_toFinset_of_not_isDiag- An unordered pair whose two components are distinct has exactly 2 elements when converted to a finite set.
G.not_isDiag_of_mem_edgeSet- An edge in a simple graph is not a loop (its endpoints are distinct).
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
G.mem_incidenceFinset- An edge belongs to the incidence finset of a vertex if and only if it belongs to the vertex's incidence set.
G.edge_mem_incidenceSet_iff- An edge belongs to the incidence set of a vertex if and only if that vertex is an endpoint of the edge.
Finset.mem_filter.mp- If an element belongs to a filtered finset, then it satisfies the filtering predicate.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
G.card_incidenceFinset_eq_degree- The cardinality of the incidence finset of a vertex equals its degree.
G.degree_le_maxDegree- The degree of any vertex in a simple graph is bounded above by the graph's maximum degree.
- In Lean, an edge in G.edgeSet is formally a subtype term, whereas G.incidenceFinset contains unordered pairs in Sym2 V. The proof explicitly uses Finset.card_le_card_of_injOn with the coercion to relate the cardinality of the filtered edge set to the incidence finset.
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.
open scoped BigOperatorstheorem simple_graph_exists_edge_tail_capacity {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : 2 ≤ G.maxDegree) : ∃ f : G.edgeSet → V, (∀ e : G.edgeSet, f e ∈ (e : Sym2 V)) ∧ ∀ v, (Finset.univ.filter (fun e => f e = v)).card ≤ G.maxDegree - 1 := by classical apply finite_two_incidence_capacity_assignment (fun (e : G.edgeSet) v => v ∈ (e : Sym2 V)) G.maxDegree hd · intro e have h : Finset.univ.filter (fun v => v ∈ (e : Sym2 V)) = (e : Sym2 V).toFinset := by ext v simp rw [h] exact Sym2.card_toFinset_of_not_isDiag _ (G.not_isDiag_of_mem_edgeSet e.property) · intro v calc (Finset.univ.filter (fun e : G.edgeSet => v ∈ (e : Sym2 V))).card ≤ (G.incidenceFinset v).card := by apply Finset.card_le_card_of_injOn (fun e : G.edgeSet => (e : Sym2 V)) · intro e he change (e : Sym2 V) ∈ G.incidenceFinset v rw [G.mem_incidenceFinset, G.edge_mem_incidenceSet_iff] exact (Finset.mem_filter.mp he).2 · intro e _ e' _ he exact Subtype.ext he _ = G.degree v := G.card_incidenceFinset_eq_degree v _ ≤ G.maxDegree := G.degree_le_maxDegree v