AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_closed_neighborhood_edge_count

theoremverified

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

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

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

    lines 4–7

    uses SimpleGraph.map_edgeFinset_induce, Finset.card_map

      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]
  2. 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.

    lines 8–35

    uses Sym2.ind, G.adj_comm

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

    lines 36–50

    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_incidenceSet

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

    lines 51–53

    uses Finset.card_inter_add_card_sdiff

      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]
  5. 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)|.

    lines 54–63

      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

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