simple_graph_endpoint_sum_edges_subset
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.
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.
uses
regular_graph_compl_regular_iffsimple_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|.
- The proof uses an automated tactic script (`first | ...`) that tries several combinations referencing `regular_graph_compl_regular_iff`. That lemma is an artifact of automated script generation and is completely unused: the branch that succeeds simply unfolds the definition of `simple_graph_endpoint_sum_edges` and simplifies the goal using the fact that any filtered finset is a subset of the original 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 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)