graph_interval_index_eq_choose_two_add_col
For every connected finite graph G on n vertices, the interval index Int(G) equals (n choose 2) + col(G).
Statement
theorem graph_interval_index_eq_choose_two_add_col {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) : graph_interval_index G = (Fintype.card V).choose 2 + graph_col G
- Formalizes
- arXiv:2610.39966 Lemma 4
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_interval_indexThe interval index of a finite graph G is the sum over all 2-element subsets {u, v} of vertices of |I(u, v)| - 1, where I(u, v) is the…
- graph_colThe collinear count col(G) of a finite graph G is the number of 3-element subsets {x, y, z} of vertices such that one of the three…
- graph_collinear_middle_uniqueAmong three pairwise distinct vertices x, y, z in a connected graph G, if y lies between x and z (i.e. d(x,y) + d(y,z) = d(x,z)), then x…
Read back from the Lean
For every finite type $V$ and every simple graph $G$ on $V$, if $G$ is connected, then the graph interval index of $G$ equals $\binom{|V|}{2} + \operatorname{graph\_col}(G)$, where: - the graph interval index of $G$ is the sum over all 2-element subsets $\{u, v\} \subseteq V$ of $(|I(u, v)| - 1)$, with $I(u, v) = \{w \in V \mid G.\operatorname{dist}(u, w) + G.\operatorname{dist}(w, v) = G.\operatorname{dist}(u, v)\}$ being the metric interval between $u$ and $v$; - $\operatorname{graph\_col}(G)$ is the number of 3-element subsets $s \subseteq V$ that contain three distinct vertices $x, y, z$ such that $y$ lies on a shortest path between $x$ and $z$ (that is, $G.\operatorname{dist}(x, y) + G.\operatorname{dist}(y, z) = G.\operatorname{dist}(x, z)$).
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 interval index is the sum over all pairs uv of |I(uv)| - 1, which equals 1 + |I(uv) \ uv|. Summing 1 over all pairs gives (n choose 2). The sum of |I(uv) \ uv| counts the collinear triples since each collinear triple has a unique pair of endpoints in a connected graph.
card_T
By Finset.card_image_of_injOn, the image of w ↦ uv ∪ {w} on I(uv) \ uv has the same cardinality as I(uv) \ uv because subtracting uv recovers {w}.
uses
Finset.card_image_of_injOn,Finset.mem_coe,Finset.mem_sdiff,Finset.singleton_inj.mpapply Finset.card_image_of_injOn intro w1 hw1 w2 hw2 heq rw [Finset.mem_coe, Finset.mem_sdiff] at hw1 hw2 dsimp at heq have h_sdiff (w : V) (hw : w ∉ uv) : (insert w uv) \ uv = {w} := by ext x; simp [hw] have h1 := h_sdiff w1 hw1.2 have h2 := h_sdiff w2 hw2.2 rw [heq] at h1 rw [h1] at h2 exact Finset.singleton_inj.mp h2
T_pairwise_disjoint
Pairwise disjointness of T(uv).
uses
Function.onFun,Finset.disjoint_iff_ne,Finset.mem_sdiff,Finset.mem_filter.mp,Finset.mem_insert_self,Finset.card_eq_two.mp,Finset.mem_insert_of_mem,Finset.mem_filter,Ne.symm,graph_collinear_middle_uniqueintro uv1 huv1 uv2 huv2 hne rw [Function.onFun, Finset.disjoint_iff_ne] rintro s hs1 _ hs2 rfl simp only [graph_interval_index_eq_choose_two_add_col_T, Finset.mem_image] at hs1 hs2 rcases hs1 with ⟨w1, hw1, rfl⟩ rcases hs2 with ⟨w2, hw2, heq⟩ rw [Finset.mem_sdiff] at hw1 hw2 have huv1_card : uv1.card = 2 := (Finset.mem_filter.mp huv1).2 have huv2_card : uv2.card = 2 := (Finset.mem_filter.mp huv2).2 by_cases hw : w1 = w2 · subst hw have : uv1 = uv2 := by have h1 : (insert w1 uv1) \ {w1} = uv1 := by ext x; simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton]; aesop have h2 : (insert w1 uv2) \ {w1} = uv2 := by ext x; simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton]; aesop rw [← h1, ← heq, h2] exact hne this · have hw2_in_uv1 : w2 ∈ uv1 := by have : w2 ∈ insert w2 uv2 := Finset.mem_insert_self w2 uv2 rw [heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (hw h.symm).elim | inr h => exact h have hw1_in_uv2 : w1 ∈ uv2 := by have : w1 ∈ insert w1 uv1 := Finset.mem_insert_self w1 uv1 rw [← heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (hw h).elim | inr h => exact h obtain ⟨t, ht_uv1, ht_ne_w2⟩ : ∃ t ∈ uv1, t ≠ w2 := by rcases Finset.card_eq_two.mp huv1_card with ⟨a, b, hab, rfl⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hw2_in_uv1 rcases hw2_in_uv1 with rfl | rfl · exact ⟨b, by simp, hab.symm⟩ · exact ⟨a, by simp, hab⟩ have ht_ne_w1 : t ≠ w1 := by rintro rfl exact hw1.2 ht_uv1 have ht_in_uv2 : t ∈ uv2 := by have : t ∈ insert w1 uv1 := Finset.mem_insert_of_mem ht_uv1 rw [← heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (ht_ne_w2 h).elim | inr h => exact h have hw1_I : w1 ∈ graph_interval_index_eq_choose_two_add_col_I G uv1 := hw1.1 dsimp [graph_interval_index_eq_choose_two_add_col_I] at hw1_I rw [Finset.mem_filter] at hw1_I have h_w1_dist := hw1_I.2 w2 hw2_in_uv1 t ht_uv1 (Ne.symm ht_ne_w2) have hw2_I : w2 ∈ graph_interval_index_eq_choose_two_add_col_I G uv2 := hw2.1 dsimp [graph_interval_index_eq_choose_two_add_col_I] at hw2_I rw [Finset.mem_filter] at hw2_I have h_w2_dist := hw2_I.2 w1 hw1_in_uv2 t ht_in_uv2 ht_ne_w1.symm have h_uniq := @graph_collinear_middle_unique V G hG w1 w2 t hw ht_ne_w2.symm ht_ne_w1.symm h_w2_dist exact h_uniq h_w1_dist
biUnion_T_eq
Equality with collinear triples.
uses
Finset.mem_biUnion,Finset.card_eq_two.mp,Finset.card_insert_of_notMem,Finset.mem_univ,Finset.card_pair,SimpleGraph.dist_comm,add_comm,Finset.eq_of_subset_of_card_leext s simp only [Finset.mem_biUnion, graph_interval_index_eq_choose_two_add_col_P2, graph_interval_index_eq_choose_two_add_col_T, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_sdiff] constructor · intro h rcases h with ⟨uv, huv2, w, ⟨hwI, hw_not_in⟩, rfl⟩ have h_two := Finset.card_eq_two.mp huv2 rcases h_two with ⟨x, z, hxz, huv_eq⟩ have hcard : (insert w uv).card = 3 := by rw [Finset.card_insert_of_notMem hw_not_in, huv2] have hx_uv : x ∈ uv := by rw [huv_eq]; simp have hz_uv : z ∈ uv := by rw [huv_eq]; simp have hw_ne_x : w ≠ x := by rintro rfl; exact hw_not_in hx_uv have hw_ne_z : w ≠ z := by rintro rfl; exact hw_not_in hz_uv refine ⟨hcard, w, Finset.mem_insert_self w _, x, Finset.mem_insert_of_mem hx_uv, z, Finset.mem_insert_of_mem hz_uv, hw_ne_x.symm, hw_ne_z, hxz, ?_⟩ dsimp [graph_interval_index_eq_choose_two_add_col_I] at hwI rw [Finset.mem_filter] at hwI exact hwI.2 x hx_uv z hz_uv hxz · rintro ⟨hcard, y, hy, x, hx, z, hz, hxy, hyz, hxz, hdist⟩ refine ⟨{x, z}, Finset.card_pair hxz, y, ⟨?_, ?_⟩, ?_⟩ · dsimp [graph_interval_index_eq_choose_two_add_col_I] rw [Finset.mem_filter] refine ⟨Finset.mem_univ y, ?_⟩ intro u hu v hv huv_ne simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl <;> rcases hv with rfl | rfl · contradiction · exact hdist · rw [SimpleGraph.dist_comm (u := u) (v := y), SimpleGraph.dist_comm (u := y) (v := v), SimpleGraph.dist_comm (u := u) (v := v), add_comm] exact hdist · contradiction · intro h simp only [Finset.mem_insert, Finset.mem_singleton] at h rcases h with rfl | rfl · exact hxy.symm rfl · exact hyz rfl · have hsub : (insert y {x, z} : Finset V) ⊆ s := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl <;> assumption have h3 : (insert y {x, z} : Finset V).card = 3 := by have hy_not : y ∉ ({x, z} : Finset V) := by simp [hxy.symm, hyz] rw [Finset.card_insert_of_notMem hy_not, Finset.card_pair hxz] exact Finset.eq_of_subset_of_card_le hsub (by rw [hcard, h3])
I_card_sub_one
Cardinality minus 1.
uses
Finset.mem_filter.mp,Finset.card_eq_two.mp,SimpleGraph.dist_self,zero_add,add_zero,Finset.card_sdiff_add_card_eq_card1 + (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by have huv2 : uv.card = 2 := (Finset.mem_filter.mp huv).2 have hsub : uv ⊆ graph_interval_index_eq_choose_two_add_col_I G uv := by intro w hw dsimp [graph_interval_index_eq_choose_two_add_col_I] simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro u hu v hv huv_ne obtain rfl | rfl : w = u ∨ w = v := by rcases Finset.card_eq_two.mp huv2 with ⟨x, y, hxy, rfl⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hw hu hv aesop · rw [SimpleGraph.dist_self, zero_add] · rw [SimpleGraph.dist_self, add_zero] have hcard : (graph_interval_index_eq_choose_two_add_col_I G uv).card = (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card + 2 := by rw [← huv2] exact (Finset.card_sdiff_add_card_eq_card hsub).symm omega
card_P2
Card of P2.
uses
Finset.powersetCard,Finset.card_powersetCard,Finset.card_univhave : graph_interval_index_eq_choose_two_add_col_P2 V = Finset.powersetCard 2 Finset.univ := by ext s; simp [graph_interval_index_eq_choose_two_add_col_P2, Finset.mem_powersetCard] rw [this, Finset.card_powersetCard, Finset.card_univ]
main
Main theorem.
uses
Finset.sum_congr,graph_interval_index_eq_choose_two_add_col_I_card_sub_one,Finset.sum_add_distrib,graph_interval_index_eq_choose_two_add_col_card_P2,graph_interval_index_eq_choose_two_add_col_biUnion_T_eq,Finset.card_biUnion,graph_interval_index_eq_choose_two_add_col_T_pairwise_disjoint,graph_interval_index_eq_choose_two_add_col_card_Thave h_int : graph_interval_index G = (Fintype.card V).choose 2 + ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by unfold graph_interval_index change (∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, ((graph_interval_index_eq_choose_two_add_col_I G uv).card - 1)) = (Fintype.card V).choose 2 + ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card have h1 : (∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, ((graph_interval_index_eq_choose_two_add_col_I G uv).card - 1)) = ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (1 + (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card) := by apply Finset.sum_congr rfl intro uv huv exact graph_interval_index_eq_choose_two_add_col_I_card_sub_one G uv huv rw [h1, Finset.sum_add_distrib] simp [graph_interval_index_eq_choose_two_add_col_card_P2] have h_col : graph_col G = ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by unfold graph_col rw [← graph_interval_index_eq_choose_two_add_col_biUnion_T_eq] rw [Finset.card_biUnion (graph_interval_index_eq_choose_two_add_col_T_pairwise_disjoint G hG)] apply Finset.sum_congr rfl intro uv huv exact graph_interval_index_eq_choose_two_add_col_card_T G uv rw [h_int, h_col]
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 Classicaldef graph_interval_index_eq_choose_two_add_col_P2 (V : Type*) [Fintype V] : Finset (Finset V) := (Finset.univ : Finset (Finset V)).filter (·.card = 2)noncomputable def graph_interval_index_eq_choose_two_add_col_I {V : Type*} [Fintype V] (G : SimpleGraph V) (uv : Finset V) : Finset V := Finset.univ.filter (fun w => ∀ u ∈ uv, ∀ v ∈ uv, u ≠ v → G.dist u w + G.dist w v = G.dist u v)noncomputable def graph_interval_index_eq_choose_two_add_col_T {V : Type*} [Fintype V] (G : SimpleGraph V) (uv : Finset V) : Finset (Finset V) := (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).image (fun w => insert w uv)theorem graph_interval_index_eq_choose_two_add_col_card_T {V : Type*} [Fintype V] (G : SimpleGraph V) (uv : Finset V) : (graph_interval_index_eq_choose_two_add_col_T G uv).card = (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by apply Finset.card_image_of_injOn intro w1 hw1 w2 hw2 heq rw [Finset.mem_coe, Finset.mem_sdiff] at hw1 hw2 dsimp at heq have h_sdiff (w : V) (hw : w ∉ uv) : (insert w uv) \ uv = {w} := by ext x; simp [hw] have h1 := h_sdiff w1 hw1.2 have h2 := h_sdiff w2 hw2.2 rw [heq] at h1 rw [h1] at h2 exact Finset.singleton_inj.mp h2theorem graph_interval_index_eq_choose_two_add_col_T_pairwise_disjoint {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) : (graph_interval_index_eq_choose_two_add_col_P2 V : Set (Finset V)).PairwiseDisjoint (graph_interval_index_eq_choose_two_add_col_T G) := by intro uv1 huv1 uv2 huv2 hne rw [Function.onFun, Finset.disjoint_iff_ne] rintro s hs1 _ hs2 rfl simp only [graph_interval_index_eq_choose_two_add_col_T, Finset.mem_image] at hs1 hs2 rcases hs1 with ⟨w1, hw1, rfl⟩ rcases hs2 with ⟨w2, hw2, heq⟩ rw [Finset.mem_sdiff] at hw1 hw2 have huv1_card : uv1.card = 2 := (Finset.mem_filter.mp huv1).2 have huv2_card : uv2.card = 2 := (Finset.mem_filter.mp huv2).2 by_cases hw : w1 = w2 · subst hw have : uv1 = uv2 := by have h1 : (insert w1 uv1) \ {w1} = uv1 := by ext x; simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton]; aesop have h2 : (insert w1 uv2) \ {w1} = uv2 := by ext x; simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton]; aesop rw [← h1, ← heq, h2] exact hne this · have hw2_in_uv1 : w2 ∈ uv1 := by have : w2 ∈ insert w2 uv2 := Finset.mem_insert_self w2 uv2 rw [heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (hw h.symm).elim | inr h => exact h have hw1_in_uv2 : w1 ∈ uv2 := by have : w1 ∈ insert w1 uv1 := Finset.mem_insert_self w1 uv1 rw [← heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (hw h).elim | inr h => exact h obtain ⟨t, ht_uv1, ht_ne_w2⟩ : ∃ t ∈ uv1, t ≠ w2 := by rcases Finset.card_eq_two.mp huv1_card with ⟨a, b, hab, rfl⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hw2_in_uv1 rcases hw2_in_uv1 with rfl | rfl · exact ⟨b, by simp, hab.symm⟩ · exact ⟨a, by simp, hab⟩ have ht_ne_w1 : t ≠ w1 := by rintro rfl exact hw1.2 ht_uv1 have ht_in_uv2 : t ∈ uv2 := by have : t ∈ insert w1 uv1 := Finset.mem_insert_of_mem ht_uv1 rw [← heq] at this simp only [Finset.mem_insert] at this cases this with | inl h => exact (ht_ne_w2 h).elim | inr h => exact h have hw1_I : w1 ∈ graph_interval_index_eq_choose_two_add_col_I G uv1 := hw1.1 dsimp [graph_interval_index_eq_choose_two_add_col_I] at hw1_I rw [Finset.mem_filter] at hw1_I have h_w1_dist := hw1_I.2 w2 hw2_in_uv1 t ht_uv1 (Ne.symm ht_ne_w2) have hw2_I : w2 ∈ graph_interval_index_eq_choose_two_add_col_I G uv2 := hw2.1 dsimp [graph_interval_index_eq_choose_two_add_col_I] at hw2_I rw [Finset.mem_filter] at hw2_I have h_w2_dist := hw2_I.2 w1 hw1_in_uv2 t ht_in_uv2 ht_ne_w1.symm have h_uniq := @graph_collinear_middle_unique V G hG w1 w2 t hw ht_ne_w2.symm ht_ne_w1.symm h_w2_dist exact h_uniq h_w1_disttheorem graph_interval_index_eq_choose_two_add_col_biUnion_T_eq {V : Type*} [Fintype V] (G : SimpleGraph V) : (graph_interval_index_eq_choose_two_add_col_P2 V).biUnion (graph_interval_index_eq_choose_two_add_col_T G) = (Finset.univ : Finset (Finset V)).filter (fun s => s.card = 3 ∧ ∃ y ∈ s, ∃ x ∈ s, ∃ z ∈ s, x ≠ y ∧ y ≠ z ∧ x ≠ z ∧ G.dist x y + G.dist y z = G.dist x z) := by ext s simp only [Finset.mem_biUnion, graph_interval_index_eq_choose_two_add_col_P2, graph_interval_index_eq_choose_two_add_col_T, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_sdiff] constructor · intro h rcases h with ⟨uv, huv2, w, ⟨hwI, hw_not_in⟩, rfl⟩ have h_two := Finset.card_eq_two.mp huv2 rcases h_two with ⟨x, z, hxz, huv_eq⟩ have hcard : (insert w uv).card = 3 := by rw [Finset.card_insert_of_notMem hw_not_in, huv2] have hx_uv : x ∈ uv := by rw [huv_eq]; simp have hz_uv : z ∈ uv := by rw [huv_eq]; simp have hw_ne_x : w ≠ x := by rintro rfl; exact hw_not_in hx_uv have hw_ne_z : w ≠ z := by rintro rfl; exact hw_not_in hz_uv refine ⟨hcard, w, Finset.mem_insert_self w _, x, Finset.mem_insert_of_mem hx_uv, z, Finset.mem_insert_of_mem hz_uv, hw_ne_x.symm, hw_ne_z, hxz, ?_⟩ dsimp [graph_interval_index_eq_choose_two_add_col_I] at hwI rw [Finset.mem_filter] at hwI exact hwI.2 x hx_uv z hz_uv hxz · rintro ⟨hcard, y, hy, x, hx, z, hz, hxy, hyz, hxz, hdist⟩ refine ⟨{x, z}, Finset.card_pair hxz, y, ⟨?_, ?_⟩, ?_⟩ · dsimp [graph_interval_index_eq_choose_two_add_col_I] rw [Finset.mem_filter] refine ⟨Finset.mem_univ y, ?_⟩ intro u hu v hv huv_ne simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl <;> rcases hv with rfl | rfl · contradiction · exact hdist · rw [SimpleGraph.dist_comm (u := u) (v := y), SimpleGraph.dist_comm (u := y) (v := v), SimpleGraph.dist_comm (u := u) (v := v), add_comm] exact hdist · contradiction · intro h simp only [Finset.mem_insert, Finset.mem_singleton] at h rcases h with rfl | rfl · exact hxy.symm rfl · exact hyz rfl · have hsub : (insert y {x, z} : Finset V) ⊆ s := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl <;> assumption have h3 : (insert y {x, z} : Finset V).card = 3 := by have hy_not : y ∉ ({x, z} : Finset V) := by simp [hxy.symm, hyz] rw [Finset.card_insert_of_notMem hy_not, Finset.card_pair hxz] exact Finset.eq_of_subset_of_card_le hsub (by rw [hcard, h3])theorem graph_interval_index_eq_choose_two_add_col_I_card_sub_one {V : Type*} [Fintype V] (G : SimpleGraph V) (uv : Finset V) (huv : uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V) : (graph_interval_index_eq_choose_two_add_col_I G uv).card - 1 = 1 + (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by have huv2 : uv.card = 2 := (Finset.mem_filter.mp huv).2 have hsub : uv ⊆ graph_interval_index_eq_choose_two_add_col_I G uv := by intro w hw dsimp [graph_interval_index_eq_choose_two_add_col_I] simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro u hu v hv huv_ne obtain rfl | rfl : w = u ∨ w = v := by rcases Finset.card_eq_two.mp huv2 with ⟨x, y, hxy, rfl⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hw hu hv aesop · rw [SimpleGraph.dist_self, zero_add] · rw [SimpleGraph.dist_self, add_zero] have hcard : (graph_interval_index_eq_choose_two_add_col_I G uv).card = (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card + 2 := by rw [← huv2] exact (Finset.card_sdiff_add_card_eq_card hsub).symm omegatheorem graph_interval_index_eq_choose_two_add_col_card_P2 (V : Type*) [Fintype V] : (graph_interval_index_eq_choose_two_add_col_P2 V).card = (Fintype.card V).choose 2 := by have : graph_interval_index_eq_choose_two_add_col_P2 V = Finset.powersetCard 2 Finset.univ := by ext s; simp [graph_interval_index_eq_choose_two_add_col_P2, Finset.mem_powersetCard] rw [this, Finset.card_powersetCard, Finset.card_univ]/-- The interval index of a connected graph equals (n choose 2) plus the number of collinear triples (Lemma 4). -/theorem graph_interval_index_eq_choose_two_add_col {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) : graph_interval_index G = (Fintype.card V).choose 2 + graph_col G := by have h_int : graph_interval_index G = (Fintype.card V).choose 2 + ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by unfold graph_interval_index change (∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, ((graph_interval_index_eq_choose_two_add_col_I G uv).card - 1)) = (Fintype.card V).choose 2 + ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card have h1 : (∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, ((graph_interval_index_eq_choose_two_add_col_I G uv).card - 1)) = ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (1 + (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card) := by apply Finset.sum_congr rfl intro uv huv exact graph_interval_index_eq_choose_two_add_col_I_card_sub_one G uv huv rw [h1, Finset.sum_add_distrib] simp [graph_interval_index_eq_choose_two_add_col_card_P2] have h_col : graph_col G = ∑ uv ∈ graph_interval_index_eq_choose_two_add_col_P2 V, (graph_interval_index_eq_choose_two_add_col_I G uv \ uv).card := by unfold graph_col rw [← graph_interval_index_eq_choose_two_add_col_biUnion_T_eq] rw [Finset.card_biUnion (graph_interval_index_eq_choose_two_add_col_T_pairwise_disjoint G hG)] apply Finset.sum_congr rfl intro uv huv exact graph_interval_index_eq_choose_two_add_col_card_T G uv rw [h_int, h_col]