AFTD Auto-Formalizing Theoretical Domains

simple_graph_endpoint_sum_edges_subset

theoremverified

For any finite simple graph G, vertex labeling φ : V → ℕ, and natural number r, the finset simple_graph_endpoint_sum_edges G φ r is a subset of the edge finset of G.

Statement

open scoped Classical in
theorem simple_graph_endpoint_sum_edges_subset {V : Type*} [Fintype V]
    (G : SimpleGraph V) (φ : V → ℕ) (r : ℕ) :
    simple_graph_endpoint_sum_edges G φ r ⊆ G.edgeFinset
Source
arXiv:2611.16338, Section 2
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_endpoint_sum_edgesGiven a finite simple graph G and a vertex labeling φ : V → ℕ, the finset simple_graph_endpoint_sum_edges G φ r consists of all edges uv…
  • regular_graph_compl_regular_iffLet G be a simple graph on a finite vertex set V with cardinality n. If d + 1 ≤ n, then G is d-regular if and only if its complement Gᶜ is…

Read back from the Lean

For any finite type $V$, any simple graph $G$ on $V$, any vertex labeling $\phi : V \to \mathbb{N}$, and any natural number $r$, the finset of edges of $G$ whose endpoints have $\phi$-values summing to $r$ is a subset of the edge finset of $G$ (G.edgeFinset).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The set simple_graph_endpoint_sum_edges G φ r is defined by filtering G.edgeFinset according to the condition that the sum of the vertex labels at the endpoints is r. Since filtering any finite set produces a subset of that set, the result follows immediately by definition and finset simplification.

  1. The finset simple_graph_endpoint_sum_edges G φ r is a subset of G.edgeFinset. automation

    The definition of `simple_graph_endpoint_sum_edges` is unfolded, expressing it as the sub-finset of `G.edgeFinset` filtered by the condition that the sum of the endpoints' labels equals r. Since filtering any finite set by a predicate yields a subset of the original set (via `Finset.filter_subset`), simplification closes the goal.

    line 5

    uses regular_graph_compl_regular_iff

        simple_graph_endpoint_sum_edges G φ r ⊆ G.edgeFinset := by first | exact regular_graph_compl_regular_iff | (apply regular_graph_compl_regular_iff <;> assumption) | (apply regular_graph_compl_regular_iff <;> simp_all) | simpa using regular_graph_compl_regular_iff | (simp only [simple_graph_endpoint_sum_edges] at *; first | exact regular_graph_compl_regular_iff | (apply regular_graph_compl_regular_iff <;> assumption) | (apply regular_graph_compl_regular_iff <;> simp_all) | simpa using regular_graph_compl_regular_iff)
regular_graph_compl_regular_iff
A finite simple graph G is regular of degree d if and only if its complement graph is regular of degree |V| - 1 - d, provided d + 1 ≤ |V|.

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 Classical in/-- Every edge with endpoint sum r is an edge of G. -/theorem simple_graph_endpoint_sum_edges_subset {V : Type*} [Fintype V]    (G : SimpleGraph V) (φ : V → ℕ) (r : ℕ) :    simple_graph_endpoint_sum_edges G φ r ⊆ G.edgeFinset := by first | exact regular_graph_compl_regular_iff | (apply regular_graph_compl_regular_iff <;> assumption) | (apply regular_graph_compl_regular_iff <;> simp_all) | simpa using regular_graph_compl_regular_iff | (simp only [simple_graph_endpoint_sum_edges] at *; first | exact regular_graph_compl_regular_iff | (apply regular_graph_compl_regular_iff <;> assumption) | (apply regular_graph_compl_regular_iff <;> simp_all) | simpa using regular_graph_compl_regular_iff)
See it in the graphDiscuss this resultChallenge it