simple_graph_triangle_free_closed_neighborhood_edge_count
In a finite triangle-free graph, the number of edges induced by the vertices outside the closed neighborhood of v plus the sum of the degrees of the neighbors of v equals the total number of edges.
Statement
theorem simple_graph_triangle_free_closed_neighborhood_edge_count {α : Type*} [Fintype α] [DecidableEq α] (G : SimpleGraph α) [DecidableRel G.Adj] (htri : G.CliqueFree 3) (v : α) : (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card
- Source
- Closed-neighborhood edge accounting for OP-926, https://arxiv.org/abs/2401.00392, Section 2.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- simple_graph_ramsey_three_ten_forty_nine_regular_or_low_degreeA triangle-free simple graph on 40 vertices with maximum degree at most 9 is either 9-regular, or it has a vertex v of degree < 9 whose…
- simple_graph_ramsey_three_ten_forty_nine_regular_outer_edgesIn a 9-regular triangle-free simple graph on 40 vertices, for every vertex v the induced subgraph on the vertices outside the closed…
The proof, explained
The total edge set of G is partitioned into edges whose endpoints both lie in S = V \ N[v] and edges with at least one endpoint in the closed neighborhood N[v]. Because G is triangle-free, the neighborhood N(v) is an independent set, so no edge connects two neighbors of v. Consequently, every edge meeting N[v] is incident to a unique neighbor of v, partitioning these edges into the pairwise disjoint incidence sets of the vertices in N(v). Summing the degrees of the neighbors of v therefore counts all edges meeting N[v], and adding the edges induced by S yields the total edge count |E(G)|.
The number of edges in the induced subgraph G[S] equals the number of edges of G with both endpoints in S, |E(G) ∩ S²|.
We define S as the set of vertices outside the closed neighborhood of v, namely {u | u ≠ v ∧ ¬G.Adj v u}. The edges of the induced subgraph G[S] embed into G with image E(G) ∩ S² (SimpleGraph.map_edgeFinset_induce), and because an embedding of finite sets preserves cardinality (Finset.card_map), the number of edges in G[S] is |E(G) ∩ S²|.
uses
SimpleGraph.map_edgeFinset_induce,Finset.card_mapclassical let S : Set α := {u | u ≠ v ∧ ¬ G.Adj v u} have hE₁ : (G.induce S).edgeFinset.card = (G.edgeFinset ∩ S.toFinset.sym2).card := by rw [← SimpleGraph.map_edgeFinset_induce (G := G) (s := S), Finset.card_map]
The edges of G not entirely contained in S are precisely the edges incident to at least one neighbor of v: E(G) \ S² = ⋃_{u ∈ N(v)} Inc(u).
We test an arbitrary edge e = s(x, y) (using Sym2.ind). For the forward inclusion, if e is an edge of G and not both endpoints lie in S, then at least one endpoint violates the definition of S, so it equals v or is adjacent to v. If x violates the condition, then either x = v (so y is adjacent to v, placing e in Inc(y)) or x is adjacent to v (placing e in Inc(x)). The case where y violates the condition is identical by symmetry of adjacency (G.adj_comm). Conversely, if e is incident to some neighbor a of v, then a is an endpoint of e adjacent to v, so a ∉ S and thus e cannot have both endpoints in S.
uses
Sym2.ind,G.adj_commhave hEdges : G.edgeFinset \ S.toFinset.sym2 = (G.neighborFinset v).biUnion (fun u => G.incidenceFinset u) := by ext e induction e using Sym2.ind with | h x y => simp only [Finset.mem_sdiff, Finset.mem_biUnion, SimpleGraph.mem_incidenceFinset, SimpleGraph.mem_edgeFinset, Finset.mem_sym2_iff, Set.mem_toFinset, SimpleGraph.mem_neighborFinset, SimpleGraph.incidenceSet, Sym2.mem_iff, Set.mem_ofPred_eq, S, SimpleGraph.mem_edgeSet] constructor · rintro ⟨hxy, hnot⟩ push Not at hnot obtain ⟨a, ha, hav⟩ := hnot rcases ha with hax | hay · subst a by_cases hxv : x = v · subst x exact ⟨y, hxy, hxy, Or.inr rfl⟩ · exact ⟨x, hav hxv, hxy, Or.inl rfl⟩ · subst a by_cases hyv : y = v · subst y exact ⟨x, (G.adj_comm x v).1 hxy, hxy, Or.inl rfl⟩ · exact ⟨y, hav hyv, hxy, Or.inr rfl⟩ · rintro ⟨a, hva, hxy, ha⟩ refine ⟨hxy, ?_⟩ intro hall exact (hall a ha).2 hva
The cardinality of the union of incidence sets ⋃_{u ∈ N(v)} Inc(u) equals ∑_{u ∈ N(v)} deg(u).
By Finset.card_biUnion, the size of a union of pairwise disjoint finsets is the sum of their sizes, and each incidence set has size deg(u) (SimpleGraph.card_incidenceFinset_eq_degree). To establish disjointness for distinct neighbors u ≠ w of v (Finset.disjoint_left), we observe that the neighborhood of v is an independent set because G is triangle-free (G.isIndepSet_neighborSet_of_triangleFree, G.isIndepSet_iff), so u and w cannot be adjacent. If an edge e were incident to both u and w, they would have to be adjacent (G.adj_of_mem_incidenceSet), which is a contradiction.
uses
Finset.card_biUnion,Finset.sum_congr,SimpleGraph.card_incidenceFinset_eq_degree,G.isIndepSet_iff,G.isIndepSet_neighborSet_of_triangleFree,Finset.disjoint_left,G.adj_of_mem_incidenceSethave hcardUnion : ((G.neighborFinset v).biUnion (fun u => G.incidenceFinset u)).card = ∑ u ∈ G.neighborFinset v, G.degree u := by rw [Finset.card_biUnion] · apply Finset.sum_congr rfl intro u hu exact SimpleGraph.card_incidenceFinset_eq_degree G u · intro u hu w hw hne change Disjoint (G.incidenceFinset u) (G.incidenceFinset w) have hInd := (G.isIndepSet_iff).1 (G.isIndepSet_neighborSet_of_triangleFree htri v) have hnu : ¬ G.Adj u w := hInd ((G.mem_neighborFinset v u).1 hu) ((G.mem_neighborFinset v w).1 hw) hne rw [Finset.disjoint_left] intro e heu hew exact hnu (G.adj_of_mem_incidenceSet hne ((G.mem_incidenceFinset u e).1 heu) ((G.mem_incidenceFinset w e).1 hew))
|E(G) ∩ S²| + |E(G) \ S²| = |E(G)|.
For any finsets, the size of their intersection plus the size of their difference equals the size of the first set (Finset.card_inter_add_card_sdiff).
uses
Finset.card_inter_add_card_sdiffhave hcard : (G.edgeFinset ∩ S.toFinset.sym2).card + (G.edgeFinset \ S.toFinset.sym2).card = G.edgeFinset.card := by rw [Finset.card_inter_add_card_sdiff]
The number of edges in G[S] plus the sum of degrees of the neighbors of v equals the total number of edges |E(G)|.
We assemble the equality using the previous steps: replace |E(G[S])| with |E(G) ∩ S²| and the degree sum with |⋃_{u ∈ N(v)} Inc(u)|, then rewrite this union as E(G) \ S², and finally apply the set partition identity to arrive at |E(G)|.
change (G.induce S).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card calc (G.induce S).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = (G.edgeFinset ∩ S.toFinset.sym2).card + ((G.neighborFinset v).biUnion (fun u => G.incidenceFinset u)).card := by rw [hE₁, ← hcardUnion] _ = (G.edgeFinset ∩ S.toFinset.sym2).card + (G.edgeFinset \ S.toFinset.sym2).card := by rw [← hEdges] _ = G.edgeFinset.card := hcard
G.adj_comm- In a simple graph, adjacency is symmetric: u is adjacent to v if and only if v is adjacent to u.
G.adj_of_mem_incidenceSet- If two distinct vertices are both incident to the same edge, then they are adjacent.
G.isIndepSet_iff- A set of vertices is independent if and only if every pair of distinct vertices in it is non-adjacent.
G.isIndepSet_neighborSet_of_triangleFree- In a triangle-free graph, the neighborhood of any vertex is an independent set.
Finset.card_biUnion- The cardinality of a union of pairwise disjoint finite sets is the sum of their cardinalities.
Finset.card_inter_add_card_sdiff- For any finite sets s and t, |s ∩ t| + |s \ t| = |s|.
Finset.card_map- An embedding of finsets preserves cardinality.
Finset.disjoint_left- Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.sum_congr- Two sums over the same finite set are equal if their terms are equal pointwise.
SimpleGraph.card_incidenceFinset_eq_degree- The number of edges incident to a vertex u equals the degree of u.
SimpleGraph.map_edgeFinset_induce- Mapping the edge set of an induced subgraph G[s] into G yields the edges of G whose endpoints both lie in s.
Sym2.ind- Every element of the symmetric square Sym2 α is an unordered pair s(x, y) for some x, y in α.
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.
theorem simple_graph_triangle_free_closed_neighborhood_edge_count {α : Type*} [Fintype α] [DecidableEq α] (G : SimpleGraph α) [DecidableRel G.Adj] (htri : G.CliqueFree 3) (v : α) : (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card := by classical let S : Set α := {u | u ≠ v ∧ ¬ G.Adj v u} have hE₁ : (G.induce S).edgeFinset.card = (G.edgeFinset ∩ S.toFinset.sym2).card := by rw [← SimpleGraph.map_edgeFinset_induce (G := G) (s := S), Finset.card_map] have hEdges : G.edgeFinset \ S.toFinset.sym2 = (G.neighborFinset v).biUnion (fun u => G.incidenceFinset u) := by ext e induction e using Sym2.ind with | h x y => simp only [Finset.mem_sdiff, Finset.mem_biUnion, SimpleGraph.mem_incidenceFinset, SimpleGraph.mem_edgeFinset, Finset.mem_sym2_iff, Set.mem_toFinset, SimpleGraph.mem_neighborFinset, SimpleGraph.incidenceSet, Sym2.mem_iff, Set.mem_ofPred_eq, S, SimpleGraph.mem_edgeSet] constructor · rintro ⟨hxy, hnot⟩ push Not at hnot obtain ⟨a, ha, hav⟩ := hnot rcases ha with hax | hay · subst a by_cases hxv : x = v · subst x exact ⟨y, hxy, hxy, Or.inr rfl⟩ · exact ⟨x, hav hxv, hxy, Or.inl rfl⟩ · subst a by_cases hyv : y = v · subst y exact ⟨x, (G.adj_comm x v).1 hxy, hxy, Or.inl rfl⟩ · exact ⟨y, hav hyv, hxy, Or.inr rfl⟩ · rintro ⟨a, hva, hxy, ha⟩ refine ⟨hxy, ?_⟩ intro hall exact (hall a ha).2 hva have hcardUnion : ((G.neighborFinset v).biUnion (fun u => G.incidenceFinset u)).card = ∑ u ∈ G.neighborFinset v, G.degree u := by rw [Finset.card_biUnion] · apply Finset.sum_congr rfl intro u hu exact SimpleGraph.card_incidenceFinset_eq_degree G u · intro u hu w hw hne change Disjoint (G.incidenceFinset u) (G.incidenceFinset w) have hInd := (G.isIndepSet_iff).1 (G.isIndepSet_neighborSet_of_triangleFree htri v) have hnu : ¬ G.Adj u w := hInd ((G.mem_neighborFinset v u).1 hu) ((G.mem_neighborFinset v w).1 hw) hne rw [Finset.disjoint_left] intro e heu hew exact hnu (G.adj_of_mem_incidenceSet hne ((G.mem_incidenceFinset u e).1 heu) ((G.mem_incidenceFinset w e).1 hew)) have hcard : (G.edgeFinset ∩ S.toFinset.sym2).card + (G.edgeFinset \ S.toFinset.sym2).card = G.edgeFinset.card := by rw [Finset.card_inter_add_card_sdiff] change (G.induce S).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card calc (G.induce S).edgeFinset.card + (∑ u ∈ G.neighborFinset v, G.degree u) = (G.edgeFinset ∩ S.toFinset.sym2).card + ((G.neighborFinset v).biUnion (fun u => G.incidenceFinset u)).card := by rw [hE₁, ← hcardUnion] _ = (G.edgeFinset ∩ S.toFinset.sym2).card + (G.edgeFinset \ S.toFinset.sym2).card := by rw [← hEdges] _ = G.edgeFinset.card := hcard