AFTD Auto-Formalizing Theoretical Domains

simple_graph_exists_edge_tail_capacity

theoremverified

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
Used by 1

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.

  1. 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.

    lines 8–10

    uses finite_two_incidence_capacity_assignment

      classical
      apply finite_two_incidence_capacity_assignment (fun (e : G.edgeSet) v => v ∈ (e : Sym2 V))
        G.maxDegree hd
  2. 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.

    lines 11–16

    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)
  3. 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.

    lines 17–29

    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.

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

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
See it in the graphDiscuss this resultChallenge it