simple_graph_clique_four_bridge_clique_connected_card_and_sum
For n ≥ 8, the number of subsets of Fin n that induce a connected subgraph in simple_graph_clique_four_bridge_clique n is 5 * 2^(n-4) + 14, and the sum of their cardinalities is 32 + (n+24)*2^(n-5) + (n-5)*2^(n-3).
Statement
theorem simple_graph_clique_four_bridge_clique_connected_card_and_sum (n : ℕ) (hn : 8 ≤ n) : let G := simple_graph_clique_four_bridge_clique n haveI : DecidableRel G.Adj := Classical.decRel _ haveI : ∀ S : Finset (Fin n), Decidable (G.induce (S : Set (Fin n))).Connected := fun _ => Classical.dec _ (Finset.univ.filter (fun S : Finset (Fin n) => (G.induce (S : Set (Fin n))).Connected)).card = 5 * 2 ^ (n - 4) + 14 ∧ (Finset.univ.filter (fun S : Finset (Fin n) => (G.induce (S : Set (Fin n))).Connected)).sum Finset.card = 32 + (n + 24) * 2 ^ (n - 5) + (n - 5) * 2 ^ (n - 3)
- Source
- step towards simple_graph_avg_connected_induced_order_clique_four_bridge_clique
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_clique_four_bridge_cliqueThe graph on {0,…,n−1} consisting of a clique on {0,1,2,3}, a clique on {4,…,n−1}, and the edge {3,4}.
- simple_graph_clique_four_glued_clique_connected_card_and_sumFor n ≥ 7, the number of subsets of Fin n that induce a connected subgraph in simple_graph_clique_four_glued_clique n is 2^(n-4) + 2^(n-1)…
- Arena.Reachable.transReachability is transitive.
The proof, explained
The graph simple_graph_clique_four_bridge_clique n consists of a 4-clique on vertices {0, 1, 2, 3} and an (n-4)-clique on vertices {4, ..., n-1}, joined by a single bridge edge between vertex 3 and vertex 4. A subset of vertices induces a connected subgraph if and only if it is a nonempty subset of the first clique, a nonempty subset of the second clique, or contains both bridge endpoints 3 and 4. These three families of subsets are pairwise disjoint and correspond to powersets (or nonempty powersets) of known sizes. Summing their cardinalities gives 15 + (2^(n-4) - 1) + 2^(n-2) = 5 * 2^(n-4) + 14, and summing the cardinalities of all their member subsets using standard powerset sum identities yields 32 + (n + 24) * 2^(n-5) + (n - 5) * 2^(n-3).
The number of vertices in Fin n with value at most 3 is 4.
The set of vertices {x : Fin n | x.val ≤ 3} is identified with the image of Fin 4 under the canonical embedding sending i to ⟨i.val, _⟩. Because this embedding preserves values, it is injective, and therefore the cardinality of the filtered set equals the cardinality of Fin 4, which is 4.
uses
Nat.le_of_lt_succ,Finset.card_image_of_injective,Fin.exthave h : (Finset.univ.filter (fun x : Fin n => x.val ≤ 3)) = Finset.image (fun i : Fin 4 => (⟨i.val, by omega⟩ : Fin n)) Finset.univ := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro hx use ⟨x.val, by omega⟩ · rintro ⟨i, _, rfl⟩ exact Nat.le_of_lt_succ i.isLt rw [h, Finset.card_image_of_injective] · simp · intro a b hab have := congr_arg Fin.val hab exact Fin.ext this
Subsets containing both a and b are precisely the image of the powerset of α \ {a, b} under inserting a and b.
For distinct elements a and b, a subset S contains both a and b if and only if it can be represented as insert a (insert b t) for some t ⊆ α \ {a, b}. The forward direction is witnessed by t = (S \ {a}) \ {b}, and reinserting b and a recovers S; the reverse direction is immediate.
uses
Finset.insert_eraseext S simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_powerset, Finset.subset_iff, Finset.mem_erase] constructor · intro ⟨ha, hb⟩ refine ⟨(S.erase a).erase b, ?_, ?_⟩ · intro x hx simp only [Finset.mem_erase, Finset.mem_univ, and_true] at hx ⊢ exact ⟨hx.1, hx.2.1⟩ · have hb' : b ∈ S.erase a := by rw [Finset.mem_erase] exact ⟨hab.symm, hb⟩ rw [Finset.insert_erase hb', Finset.insert_erase ha] · rintro ⟨t, ht, rfl⟩ simp only [Finset.mem_insert, true_or, or_true, and_self]
Inserting distinct elements a and b into subsets disjoint from {a, b} is an injective operation.
Suppose insert a (insert b t1) = insert a (insert b t2) with t1, t2 ⊆ α \ {a, b}. Since a is not in insert b t1 or insert b t2, erasing a from both sets leaves insert b t1 = insert b t2. Then, since b is not in t1 or t2, erasing b leaves t1 = t2.
uses
Finset.erase_insertintro t1 ht1 t2 ht2 heq change insert a (insert b t1) = insert a (insert b t2) at heq rw [Finset.mem_coe, Finset.mem_powerset] at ht1 ht2 have hna1 : a ∉ insert b t1 := by simp only [Finset.mem_insert, not_or] exact ⟨hab, fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (ht1 ha)).2).1 rfl⟩ have hna2 : a ∉ insert b t2 := by simp only [Finset.mem_insert, not_or] exact ⟨hab, fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (ht2 ha)).2).1 rfl⟩ have h1 : (insert a (insert b t1)).erase a = insert b t1 := Finset.erase_insert hna1 have h2 : (insert a (insert b t2)).erase a = insert b t2 := Finset.erase_insert hna2 have h12 : insert b t1 = insert b t2 := by rw [← h1, ← h2, heq] have hnb1 : b ∉ t1 := fun hb => (Finset.mem_erase.mp (ht1 hb)).1 rfl have hnb2 : b ∉ t2 := fun hb => (Finset.mem_erase.mp (ht2 hb)).1 rfl rw [← Finset.erase_insert hnb1, ← Finset.erase_insert hnb2, h12]
A connected induced subgraph must be contained in the left clique, contained in the right clique, or contain both bridge endpoints v3 and v4.
Let H be the subgraph induced by S. If both v3 and v4 belong to S, the claim holds. Otherwise, no edge in H can cross between {x | x.val ≤ 3} and {x | 4 ≤ x.val}, as the only cross edge in the graph is between v3 and v4. Since H is connected and nonempty, picking an arbitrary vertex x ∈ S shows that every vertex reachable from x must remain on the same side as x, so S is entirely within one of the two cliques.
uses
simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closedclassical let H := (simple_graph_clique_four_bridge_clique n).induce (S : Set (Fin n)) constructor · intro hc by_cases hb : v3 ∈ S ∧ v4 ∈ S · exact Or.inr (Or.inr hb) have no_cross (v w : ↥(S : Set (Fin n))) (hv : v.1.val ≤ 3) (hw : 4 ≤ w.1.val) (hadj : H.Adj v w) : False := by change v.1 ≠ w.1 ∧ ((v.1.val ≤ 3 ∧ w.1.val ≤ 3) ∨ (4 ≤ v.1.val ∧ 4 ≤ w.1.val) ∨ (v.1.val = 3 ∧ w.1.val = 4) ∨ (v.1.val = 4 ∧ w.1.val = 3)) at hadj have he3 : v.1 = v3 := Fin.ext (by omega) have he4 : w.1 = v4 := Fin.ext (by omega) have hm3 : v3 ∈ S := he3 ▸ v.2 have hm4 : v4 ∈ S := he4 ▸ w.2 exact hb ⟨hm3,hm4⟩ obtain ⟨⟨x,hxS⟩⟩ := hc.nonempty by_cases hx : x.val ≤ 3 · left refine ⟨⟨x,hxS⟩,fun y hy => ?_⟩ exact simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed (G := H) (T := {z | z.1.val ≤ 3}) (fun v hv w hadj => by change v.1.val ≤ 3 at hv change w.1.val ≤ 3 by_contra hw exact no_cross v w hv (by omega) hadj) (u := ⟨x,hxS⟩) (by exact hx) (hc.preconnected _ ⟨y,hy⟩) · right; left refine ⟨⟨x,hxS⟩,fun y hy => ?_⟩ exact simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed (G := H) (T := {z | 4 ≤ z.1.val}) (fun v hv w hadj => by change 4 ≤ v.1.val at hv change 4 ≤ w.1.val by_contra hw exact no_cross w v (by omega) hv hadj.symm) (u := ⟨x,hxS⟩) (by change 4 ≤ x.val; omega) (hc.preconnected _ ⟨y,hy⟩)
Conversely, any nonempty subset of the left clique, any nonempty subset of the right clique, or any subset containing both v3 and v4 induces a connected subgraph.
Any nonempty subset of a clique is itself a clique, hence connected. If S contains both v3 and v4, then every vertex with value at most 3 in S is adjacent to v3, every vertex with value at least 4 in S is adjacent to v4, and v4 is adjacent to v3 via the bridge edge. Thus every vertex in S can reach v3, which implies all pairs in S are mutually reachable.
uses
SimpleGraph.Connected.mk,SimpleGraph.Reachable.refl,SimpleGraph.Adj.reachable,Subtype.ext· rintro (⟨hne,hleft⟩ | ⟨hne,hright⟩ | ⟨h3,h4⟩) · haveI : Nonempty ↥(S : Set (Fin n)) := hne.to_subtype refine SimpleGraph.Connected.mk (fun x y => ?_) by_cases hxy : x = y · subst y; exact SimpleGraph.Reachable.refl _ · apply SimpleGraph.Adj.reachable change x.1 ≠ y.1 ∧ ((x.1.val ≤ 3 ∧ y.1.val ≤ 3) ∨ _) exact ⟨fun he => hxy (Subtype.ext he),Or.inl ⟨hleft x.1 x.2,hleft y.1 y.2⟩⟩ · haveI : Nonempty ↥(S : Set (Fin n)) := hne.to_subtype refine SimpleGraph.Connected.mk (fun x y => ?_) by_cases hxy : x = y · subst y; exact SimpleGraph.Reachable.refl _ · apply SimpleGraph.Adj.reachable change x.1 ≠ y.1 ∧ (_ ∨ (4 ≤ x.1.val ∧ 4 ≤ y.1.val) ∨ _) exact ⟨fun he => hxy (Subtype.ext he),Or.inr (Or.inl ⟨hright x.1 x.2,hright y.1 y.2⟩)⟩ · haveI : Nonempty ↥(S : Set (Fin n)) := ⟨⟨v3,h3⟩⟩ have hL (x : ↥(S : Set (Fin n))) (hx : x.1.val ≤ 3) : H.Reachable x ⟨v3,h3⟩ := by by_cases he : x = ⟨v3,h3⟩ · rw [he] · apply SimpleGraph.Adj.reachable change x.1 ≠ v3 ∧ ((x.1.val ≤ 3 ∧ v3.val ≤ 3) ∨ _) exact ⟨fun hh => he (Subtype.ext hh),Or.inl ⟨hx,by omega⟩⟩ have hR (x : ↥(S : Set (Fin n))) (hx : 4 ≤ x.1.val) : H.Reachable x ⟨v4,h4⟩ := by by_cases he : x = ⟨v4,h4⟩ · rw [he] · apply SimpleGraph.Adj.reachable change x.1 ≠ v4 ∧ (_ ∨ (4 ≤ x.1.val ∧ 4 ≤ v4.val) ∨ _) exact ⟨fun hh => he (Subtype.ext hh),Or.inr (Or.inl ⟨hx,by omega⟩)⟩ have hbridge : H.Reachable ⟨v4,h4⟩ ⟨v3,h3⟩ := by apply SimpleGraph.Adj.reachable change v4 ≠ v3 ∧ (_ ∨ _ ∨ _ ∨ (v4.val = 4 ∧ v3.val = 3)) exact ⟨fun he => by have := congrArg Fin.val he; omega,Or.inr (Or.inr (Or.inr ⟨hv4,hv3⟩))⟩ have hgo (x : ↥(S : Set (Fin n))) : H.Reachable x ⟨v3,h3⟩ := by by_cases hx : x.1.val ≤ 3 · exact hL x hx · exact (hR x (by omega)).trans hbridge exact SimpleGraph.Connected.mk (fun x y => (hgo x).trans (hgo y).symm)For distinct a and b, the number of subsets containing both is 2^(|α| - 2), and the sum of their cardinalities is (|α| - 2) * 2^(|α| - 3) + 2 * 2^(|α| - 2).
The subsets containing both a and b biject with the powerset of U = α \ {a, b}, which has cardinality |α| - 2, giving 2^(|α| - 2) such subsets. Each such subset has cardinality |t| + 2, so the sum splits into ∑_{t ⊆ U} |t| + 2 * |powerset U|. By the identity for the sum of subset sizes, this equals (|α| - 2) * 2^(|α| - 3) + 2 * 2^(|α| - 2).
uses
Finset.card_erase_of_mem,Finset.card_univ,Finset.card_insert_of_notMem,in148_filter_pair_mem_univ_eq_image,Finset.card_image_of_injOn,in148_insert_pair_injOn,Finset.card_powerset,Finset.sum_image,Finset.sum_congr,Finset.sum_add_distrib,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_powerset,Finset.sum_const,Nat.sub_subclassical let U := (Finset.univ.erase a).erase b have hb : b ∈ Finset.univ.erase a := Finset.mem_erase.mpr ⟨hab.symm,Finset.mem_univ _⟩ have hU : U.card = Fintype.card α - 2 := by rw [Finset.card_erase_of_mem hb,Finset.card_erase_of_mem (Finset.mem_univ a),Finset.card_univ] omega have hsize (t : Finset α) (ht : t ∈ U.powerset) : (insert a (insert b t)).card = t.card+2 := by have hsub := Finset.mem_powerset.mp ht have hnb : b ∉ t := fun hb => (Finset.mem_erase.mp (hsub hb)).1 rfl have hna : a ∉ insert b t := by simp only [Finset.mem_insert,not_or] exact ⟨hab,fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (hsub ha)).2).1 rfl⟩ rw [Finset.card_insert_of_notMem hna,Finset.card_insert_of_notMem hnb] constructor · rw [in148_filter_pair_mem_univ_eq_image a b hab,Finset.card_image_of_injOn (in148_insert_pair_injOn a b hab), Finset.card_powerset,hU] · rw [in148_filter_pair_mem_univ_eq_image a b hab,Finset.sum_image (in148_insert_pair_injOn a b hab)] change ∑ t ∈ U.powerset, (insert a (insert b t)).card = _ rw [Finset.sum_congr rfl hsize,Finset.sum_add_distrib, simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_powerset, Finset.sum_const,Finset.card_powerset,hU] norm_num only [smul_eq_mul,Nat.sub_sub] <;> omega
The collection of connected induced subgraphs partitions into F1 ∪ (F2 ∪ F3).
We fix the bridge endpoints v3 = ⟨3, _⟩ and v4 = ⟨4, _⟩, the left set L = {x | x.val ≤ 3}, and the right set R = {x | 4 ≤ x.val}. By in148_connected_iff, the filter of connected induced subgraphs is precisely the union of F1 (nonempty subsets of L), F2 (nonempty subsets of R), and F3 (subsets containing both v3 and v4).
uses
Finset.filter_congr_decidable,Finset.filter_or,Finset.filter_congr,in148_connected_iffclassical dsimp only rw [Finset.filter_congr_decidable (s := Finset.univ) (p := fun S : Finset (Fin n) => (SimpleGraph.induce (↑S) (simple_graph_clique_four_bridge_clique n)).Connected) (Classical.decPred _)] set v3 : Fin n := ⟨3,by omega⟩ with hv3 set v4 : Fin n := ⟨4,by omega⟩ with hv4 have hv3val : v3.val = 3 := rfl have hv4val : v4.val = 4 := rfl have hv34 : v3 ≠ v4 := by intro he; have := congrArg Fin.val he; omega set L : Finset (Fin n) := Finset.univ.filter (fun x : Fin n => x.val ≤ 3) with hL set R : Finset (Fin n) := Finset.univ.filter (fun x : Fin n => 4 ≤ x.val) with hR set F1 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => S.Nonempty ∧ ∀ x ∈ S, x.val ≤ 3) with hF1 set F2 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => S.Nonempty ∧ ∀ x ∈ S, 4 ≤ x.val) with hF2 set F3 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => v3 ∈ S ∧ v4 ∈ S) with hF3 have hT : Finset.univ.filter (fun S : Finset (Fin n) => (SimpleGraph.induce (↑S) (simple_graph_clique_four_bridge_clique n)).Connected) = F1 ∪ (F2 ∪ F3) := by rw [hF1,hF2,hF3,← Finset.filter_or,← Finset.filter_or] exact Finset.filter_congr (fun S _ => in148_connected_iff n v3 v4 hv3val hv4val S)
The families F1, F2, and F3 are pairwise disjoint.
Every subset in F2 consists entirely of vertices with value at least 4, so v3 (which has value 3) cannot belong to it, making F2 disjoint from F3. Every subset in F1 consists entirely of vertices with value at most 3; because it is nonempty, it cannot be contained in F2, nor can it contain v4 (which has value 4), so F1 is disjoint from F2 ∪ F3.
uses
Finset.disjoint_left,Finset.mem_unionhave hd23 : Disjoint F2 F3 := by apply Finset.disjoint_left.mpr intro S hS hS' simp only [hF2,hF3,Finset.mem_filter,Finset.mem_univ,true_and] at hS hS' have := hS.2 v3 hS'.1 omega have hd1 : Disjoint F1 (F2 ∪ F3) := by apply Finset.disjoint_left.mpr intro S hS hS' simp only [hF1,Finset.mem_filter,Finset.mem_univ,true_and] at hS rcases Finset.mem_union.mp hS' with hS' | hS' · simp only [hF2,Finset.mem_filter,Finset.mem_univ,true_and] at hS' obtain ⟨x,hx⟩ := hS.1 have := hS.2 x hx have := hS'.2 x hx omega · simp only [hF3,Finset.mem_filter,Finset.mem_univ,true_and] at hS' have := hS.2 v4 hS'.2 omega
The sizes and cardinality sums of F1, F2, and F3 are computed from powerset identities.
Since |L| = 4, F1 consists of the nonempty subsets of a 4-element set, so |F1| = 2^4 - 1 = 15 and its cardinality sum is 4 * 2^3 = 32. Since |R| = n - 4, F2 gives |F2| = 2^(n-4) - 1 and cardinality sum (n - 4) * 2^(n-5). For F3, the subsets containing both v3 and v4 have cardinality 2^(n-2) and cardinality sum (n - 2) * 2^(n-3) + 2 * 2^(n-2) by in148_pair_card_sum.
uses
in148_card_filter_val_le_three,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_filter_val_ge_four,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset,Fintype.card_fin,in148_pair_card_sumhave hF1eq : F1 = L.powerset.filter Finset.Nonempty := by rw [hF1,hL] ext S simp only [Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_powerset,Finset.subset_iff] exact ⟨fun h => ⟨h.2,h.1⟩,fun h => ⟨h.2,h.1⟩⟩ have hF2eq : F2 = R.powerset.filter Finset.Nonempty := by rw [hF2,hR] ext S simp only [Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_powerset,Finset.subset_iff] exact ⟨fun h => ⟨h.2,h.1⟩,fun h => ⟨h.2,h.1⟩⟩ have hLc : L.card = 4 := by rw [hL]; exact in148_card_filter_val_le_three n (by omega) have hRc : R.card = n-4 := by rw [hR] exact simple_graph_clique_four_glued_clique_connected_card_and_sum_card_filter_val_ge_four n (by omega) have hF1c : F1.card = 15 := by rw [hF1eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset,hLc] norm_num have hF1s : ∑ S ∈ F1, S.card = 32 := by rw [hF1eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset,hLc] norm_num have hF2c : F2.card = 2^(n-4)-1 := by rw [hF2eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset,hRc] have hF2s : ∑ S ∈ F2, S.card = (n-4)*2^(n-5) := by rw [hF2eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset,hRc] rw [show n-4-1 = n-5 by omega] have hF3c : F3.card = 2^(n-2) := by simpa only [Fintype.card_fin] using (in148_pair_card_sum v3 v4 hv34).1 have hF3s : ∑ S ∈ F3, S.card = (n-2)*2^(n-3)+2*2^(n-2) := by simpa only [Fintype.card_fin] using (in148_pair_card_sum v3 v4 hv34).2
The total number of subsets inducing connected subgraphs is 5 * 2^(n - 4) + 14.
Because F1, F2, and F3 are pairwise disjoint, the total count is |F1| + |F2| + |F3| = 15 + (2^(n-4) - 1) + 2^(n-2). Rewriting 2^(n-2) as 4 * 2^(n-4) yields 14 + 5 * 2^(n-4).
uses
Finset.card_union_of_disjoint,pow_add,Nat.one_le_two_powconstructor · rw [hT,Finset.card_union_of_disjoint hd1,Finset.card_union_of_disjoint hd23,hF1c,hF2c,hF3c] have hp : 2^(n-2) = 4*2^(n-4) := by rw [show n-2 = (n-4)+2 by omega,pow_add] norm_num ring rw [hp] have hpos : 1 ≤ 2^(n-4) := Nat.one_le_two_pow omega
The sum of cardinalities of all subsets inducing connected subgraphs is 32 + (n + 24) * 2^(n - 5) + (n - 5) * 2^(n - 3).
Summing over the disjoint union yields 32 + (n - 4) * 2^(n-5) + (n - 2) * 2^(n-3) + 2 * 2^(n-2). Writing all powers in terms of 2^(n-5), this sum simplifies algebraically to 32 + (5n + 4) * 2^(n-5), which matches 32 + (n + 24) * 2^(n-5) + (n - 5) * 2^(n-3).
uses
Finset.sum_union,pow_add· rw [hT,Finset.sum_union hd1,Finset.sum_union hd23,hF1s,hF2s,hF3s] have hp2 : 2^(n-2) = 8*2^(n-5) := by rw [show n-2 = (n-5)+3 by omega,pow_add] norm_num ring have hp3 : 2^(n-3) = 4*2^(n-5) := by rw [show n-3 = (n-5)+2 by omega,pow_add] norm_num ring rw [hp2,hp3,show n-4 = (n-5)+1 by omega,show n-2 = (n-5)+3 by omega, show n+24 = (n-5)+29 by omega] ring
Nat.le_of_lt_succ- If m < n + 1 for natural numbers m and n, then m ≤ n.
Finset.card_image_of_injective- If f is injective, the image of a finite set s under f has the same cardinality as s.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Finset.insert_erase- For an element a in a finite set s, inserting a into s \ {a} recovers s.
Finset.erase_insert- If a is not in a finite set s, removing a from {a} ∪ s yields s.
simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed- If a vertex subset T is closed under adjacency (all neighbors of vertices in T lie in T), then any vertex reachable from T must also belong to T.
SimpleGraph.Connected.mk- A simple graph is connected if its vertex type is nonempty and every pair of vertices is connected by a path.
SimpleGraph.Reachable.refl- Every vertex in a graph is reachable from itself.
SimpleGraph.Adj.reachable- Adjacent vertices in a graph are reachable from each other.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.card_univ- The cardinality of the universal finset on a finite type α is the cardinality of α.
Finset.card_insert_of_notMem- Inserting an element not present in a finite set increases its cardinality by 1.
in148_filter_pair_mem_univ_eq_image- The collection of all subsets of α containing distinct elements a and b is the image of the powerset of α \ {a, b} under inserting b then a.
Finset.card_image_of_injOn- If f is injective on a finite set s, then the image f(s) has the same cardinality as s.
in148_insert_pair_injOn- The operation of inserting distinct elements a and b is injective on the powerset of α \ {a, b}.
Finset.card_powerset- The cardinality of the powerset of a finite set s is 2^|s|.
Finset.sum_image- Summing a function over the image of an injective map on a finset equals summing the composite function over the original finset.
Finset.sum_congr- Two sums over equal finsets with equal values on each element are equal.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set distributes into the sum of the individual sums.
simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_powerset- The sum of the cardinalities of all subsets of a finite set s is |s| * 2^(|s| - 1).
Finset.sum_const- The sum of a constant c over a finite set s equals |s| * c.
Nat.sub_sub- For natural numbers, n - m - k = n - (m + k).
Finset.filter_congr_decidable- Filtering a finset does not depend on the decidability instance of the predicate.
Finset.filter_or- Filtering by a disjunction of predicates equals the union of the sets filtered by each predicate.
Finset.filter_congr- If two predicates are equivalent on every element of a finite set, filtering by either predicate produces the same finset.
in148_connected_iff- A subset S induces a connected subgraph in simple_graph_clique_four_bridge_clique n iff S is a nonempty subset of {x | x.val ≤ 3}, a nonempty subset of {x | 4 ≤ x.val}, or contains both bridge endpoints v3 and v4.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_union- An element belongs to the union of two finsets if and only if it belongs to at least one of them.
in148_card_filter_val_le_three- The number of vertices in Fin n with value at most 3 is 4.
simple_graph_clique_four_glued_clique_connected_card_and_sum_card_filter_val_ge_four- For n ≥ 7, the number of vertices in Fin n with value at least 4 is n - 4.
simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset- The number of nonempty subsets of a finite set s is 2^|s| - 1.
simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset- The sum of the cardinalities of all nonempty subsets of a finite set s is |s| * 2^(|s| - 1).
Fintype.card_fin- The cardinality of the finite type Fin n is n.
in148_pair_card_sum- For distinct elements a and b, the number of subsets containing both is 2^(|α| - 2) and the sum of their cardinalities is (|α| - 2) * 2^(|α| - 3) + 2 * 2^(|α| - 2).
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
pow_add- For powers in a monoid, a^(m + n) = a^m * a^n.
Nat.one_le_two_pow- For any natural number n, 1 ≤ 2^n.
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
- Subsets of vertices in Fin n are represented as finite sets (Finset (Fin n)), and induced subgraphs coerce these to sets (Set (Fin n)). Classical decidability instances are used to allow filtering by the property of being connected.
- The final algebraic identities rewriting powers such as 2^(n-2) = 4 * 2^(n-4) and 2^(n-3) = 4 * 2^(n-5) to combine the terms are completed by the ring and omega tactics.
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.
private lemma in148_card_filter_val_le_three (n : ℕ) (hn : 4 ≤ n) : (Finset.univ.filter (fun x : Fin n => x.val ≤ 3)).card = 4 := by have h : (Finset.univ.filter (fun x : Fin n => x.val ≤ 3)) = Finset.image (fun i : Fin 4 => (⟨i.val, by omega⟩ : Fin n)) Finset.univ := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro hx use ⟨x.val, by omega⟩ · rintro ⟨i, _, rfl⟩ exact Nat.le_of_lt_succ i.isLt rw [h, Finset.card_image_of_injective] · simp · intro a b hab have := congr_arg Fin.val hab exact Fin.ext thisprivate lemma in148_filter_pair_mem_univ_eq_image {α : Type*} [Fintype α] [DecidableEq α] (a b : α) (hab : a ≠ b) : (Finset.univ.filter (fun S : Finset α => a ∈ S ∧ b ∈ S)) = ((Finset.univ.erase a).erase b).powerset.image (fun t => insert a (insert b t)) := by ext S simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_powerset, Finset.subset_iff, Finset.mem_erase] constructor · intro ⟨ha, hb⟩ refine ⟨(S.erase a).erase b, ?_, ?_⟩ · intro x hx simp only [Finset.mem_erase, Finset.mem_univ, and_true] at hx ⊢ exact ⟨hx.1, hx.2.1⟩ · have hb' : b ∈ S.erase a := by rw [Finset.mem_erase] exact ⟨hab.symm, hb⟩ rw [Finset.insert_erase hb', Finset.insert_erase ha] · rintro ⟨t, ht, rfl⟩ simp only [Finset.mem_insert, true_or, or_true, and_self]private lemma in148_insert_pair_injOn {α : Type*} [Fintype α] [DecidableEq α] (a b : α) (hab : a ≠ b) : Set.InjOn (fun t : Finset α => insert a (insert b t)) (((Finset.univ.erase a).erase b).powerset : Set (Finset α)) := by intro t1 ht1 t2 ht2 heq change insert a (insert b t1) = insert a (insert b t2) at heq rw [Finset.mem_coe, Finset.mem_powerset] at ht1 ht2 have hna1 : a ∉ insert b t1 := by simp only [Finset.mem_insert, not_or] exact ⟨hab, fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (ht1 ha)).2).1 rfl⟩ have hna2 : a ∉ insert b t2 := by simp only [Finset.mem_insert, not_or] exact ⟨hab, fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (ht2 ha)).2).1 rfl⟩ have h1 : (insert a (insert b t1)).erase a = insert b t1 := Finset.erase_insert hna1 have h2 : (insert a (insert b t2)).erase a = insert b t2 := Finset.erase_insert hna2 have h12 : insert b t1 = insert b t2 := by rw [← h1, ← h2, heq] have hnb1 : b ∉ t1 := fun hb => (Finset.mem_erase.mp (ht1 hb)).1 rfl have hnb2 : b ∉ t2 := fun hb => (Finset.mem_erase.mp (ht2 hb)).1 rfl rw [← Finset.erase_insert hnb1, ← Finset.erase_insert hnb2, h12]private lemma in148_connected_iff (n : ℕ) (v3 v4 : Fin n) (hv3 : v3.val = 3) (hv4 : v4.val = 4) (S : Finset (Fin n)) : ((simple_graph_clique_four_bridge_clique n).induce (S : Set (Fin n))).Connected ↔ (S.Nonempty ∧ ∀ x ∈ S, x.val ≤ 3) ∨ (S.Nonempty ∧ ∀ x ∈ S, 4 ≤ x.val) ∨ (v3 ∈ S ∧ v4 ∈ S) := by classical let H := (simple_graph_clique_four_bridge_clique n).induce (S : Set (Fin n)) constructor · intro hc by_cases hb : v3 ∈ S ∧ v4 ∈ S · exact Or.inr (Or.inr hb) have no_cross (v w : ↥(S : Set (Fin n))) (hv : v.1.val ≤ 3) (hw : 4 ≤ w.1.val) (hadj : H.Adj v w) : False := by change v.1 ≠ w.1 ∧ ((v.1.val ≤ 3 ∧ w.1.val ≤ 3) ∨ (4 ≤ v.1.val ∧ 4 ≤ w.1.val) ∨ (v.1.val = 3 ∧ w.1.val = 4) ∨ (v.1.val = 4 ∧ w.1.val = 3)) at hadj have he3 : v.1 = v3 := Fin.ext (by omega) have he4 : w.1 = v4 := Fin.ext (by omega) have hm3 : v3 ∈ S := he3 ▸ v.2 have hm4 : v4 ∈ S := he4 ▸ w.2 exact hb ⟨hm3,hm4⟩ obtain ⟨⟨x,hxS⟩⟩ := hc.nonempty by_cases hx : x.val ≤ 3 · left refine ⟨⟨x,hxS⟩,fun y hy => ?_⟩ exact simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed (G := H) (T := {z | z.1.val ≤ 3}) (fun v hv w hadj => by change v.1.val ≤ 3 at hv change w.1.val ≤ 3 by_contra hw exact no_cross v w hv (by omega) hadj) (u := ⟨x,hxS⟩) (by exact hx) (hc.preconnected _ ⟨y,hy⟩) · right; left refine ⟨⟨x,hxS⟩,fun y hy => ?_⟩ exact simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed (G := H) (T := {z | 4 ≤ z.1.val}) (fun v hv w hadj => by change 4 ≤ v.1.val at hv change 4 ≤ w.1.val by_contra hw exact no_cross w v (by omega) hv hadj.symm) (u := ⟨x,hxS⟩) (by change 4 ≤ x.val; omega) (hc.preconnected _ ⟨y,hy⟩) · rintro (⟨hne,hleft⟩ | ⟨hne,hright⟩ | ⟨h3,h4⟩) · haveI : Nonempty ↥(S : Set (Fin n)) := hne.to_subtype refine SimpleGraph.Connected.mk (fun x y => ?_) by_cases hxy : x = y · subst y; exact SimpleGraph.Reachable.refl _ · apply SimpleGraph.Adj.reachable change x.1 ≠ y.1 ∧ ((x.1.val ≤ 3 ∧ y.1.val ≤ 3) ∨ _) exact ⟨fun he => hxy (Subtype.ext he),Or.inl ⟨hleft x.1 x.2,hleft y.1 y.2⟩⟩ · haveI : Nonempty ↥(S : Set (Fin n)) := hne.to_subtype refine SimpleGraph.Connected.mk (fun x y => ?_) by_cases hxy : x = y · subst y; exact SimpleGraph.Reachable.refl _ · apply SimpleGraph.Adj.reachable change x.1 ≠ y.1 ∧ (_ ∨ (4 ≤ x.1.val ∧ 4 ≤ y.1.val) ∨ _) exact ⟨fun he => hxy (Subtype.ext he),Or.inr (Or.inl ⟨hright x.1 x.2,hright y.1 y.2⟩)⟩ · haveI : Nonempty ↥(S : Set (Fin n)) := ⟨⟨v3,h3⟩⟩ have hL (x : ↥(S : Set (Fin n))) (hx : x.1.val ≤ 3) : H.Reachable x ⟨v3,h3⟩ := by by_cases he : x = ⟨v3,h3⟩ · rw [he] · apply SimpleGraph.Adj.reachable change x.1 ≠ v3 ∧ ((x.1.val ≤ 3 ∧ v3.val ≤ 3) ∨ _) exact ⟨fun hh => he (Subtype.ext hh),Or.inl ⟨hx,by omega⟩⟩ have hR (x : ↥(S : Set (Fin n))) (hx : 4 ≤ x.1.val) : H.Reachable x ⟨v4,h4⟩ := by by_cases he : x = ⟨v4,h4⟩ · rw [he] · apply SimpleGraph.Adj.reachable change x.1 ≠ v4 ∧ (_ ∨ (4 ≤ x.1.val ∧ 4 ≤ v4.val) ∨ _) exact ⟨fun hh => he (Subtype.ext hh),Or.inr (Or.inl ⟨hx,by omega⟩)⟩ have hbridge : H.Reachable ⟨v4,h4⟩ ⟨v3,h3⟩ := by apply SimpleGraph.Adj.reachable change v4 ≠ v3 ∧ (_ ∨ _ ∨ _ ∨ (v4.val = 4 ∧ v3.val = 3)) exact ⟨fun he => by have := congrArg Fin.val he; omega,Or.inr (Or.inr (Or.inr ⟨hv4,hv3⟩))⟩ have hgo (x : ↥(S : Set (Fin n))) : H.Reachable x ⟨v3,h3⟩ := by by_cases hx : x.1.val ≤ 3 · exact hL x hx · exact (hR x (by omega)).trans hbridge exact SimpleGraph.Connected.mk (fun x y => (hgo x).trans (hgo y).symm)private lemma in148_pair_card_sum {α : Type*} [Fintype α] [DecidableEq α] (a b : α) (hab : a ≠ b) : (Finset.univ.filter (fun S : Finset α => a ∈ S ∧ b ∈ S)).card = 2 ^ (Fintype.card α - 2) ∧ ∑ S ∈ Finset.univ.filter (fun S : Finset α => a ∈ S ∧ b ∈ S), S.card = (Fintype.card α - 2) * 2 ^ (Fintype.card α - 3) + 2 * 2 ^ (Fintype.card α - 2) := by classical let U := (Finset.univ.erase a).erase b have hb : b ∈ Finset.univ.erase a := Finset.mem_erase.mpr ⟨hab.symm,Finset.mem_univ _⟩ have hU : U.card = Fintype.card α - 2 := by rw [Finset.card_erase_of_mem hb,Finset.card_erase_of_mem (Finset.mem_univ a),Finset.card_univ] omega have hsize (t : Finset α) (ht : t ∈ U.powerset) : (insert a (insert b t)).card = t.card+2 := by have hsub := Finset.mem_powerset.mp ht have hnb : b ∉ t := fun hb => (Finset.mem_erase.mp (hsub hb)).1 rfl have hna : a ∉ insert b t := by simp only [Finset.mem_insert,not_or] exact ⟨hab,fun ha => (Finset.mem_erase.mp (Finset.mem_erase.mp (hsub ha)).2).1 rfl⟩ rw [Finset.card_insert_of_notMem hna,Finset.card_insert_of_notMem hnb] constructor · rw [in148_filter_pair_mem_univ_eq_image a b hab,Finset.card_image_of_injOn (in148_insert_pair_injOn a b hab), Finset.card_powerset,hU] · rw [in148_filter_pair_mem_univ_eq_image a b hab,Finset.sum_image (in148_insert_pair_injOn a b hab)] change ∑ t ∈ U.powerset, (insert a (insert b t)).card = _ rw [Finset.sum_congr rfl hsize,Finset.sum_add_distrib, simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_powerset, Finset.sum_const,Finset.card_powerset,hU] norm_num only [smul_eq_mul,Nat.sub_sub] <;> omega/-- For n ≥ 8, the number of subsets of Fin n that induce a connected subgraph in simple_graph_clique_four_bridge_clique n is 5 * 2^(n-4) + 14, and the sum of their cardinalities is 32 + (n+24)*2^(n-5) + (n-5)*2^(n-3). -/theorem simple_graph_clique_four_bridge_clique_connected_card_and_sum (n : ℕ) (hn : 8 ≤ n) : let G := simple_graph_clique_four_bridge_clique n haveI : DecidableRel G.Adj := Classical.decRel _ haveI : ∀ S : Finset (Fin n), Decidable (G.induce (S : Set (Fin n))).Connected := fun _ => Classical.dec _ (Finset.univ.filter (fun S : Finset (Fin n) => (G.induce (S : Set (Fin n))).Connected)).card = 5 * 2 ^ (n - 4) + 14 ∧ (Finset.univ.filter (fun S : Finset (Fin n) => (G.induce (S : Set (Fin n))).Connected)).sum Finset.card = 32 + (n + 24) * 2 ^ (n - 5) + (n - 5) * 2 ^ (n - 3) := by classical dsimp only rw [Finset.filter_congr_decidable (s := Finset.univ) (p := fun S : Finset (Fin n) => (SimpleGraph.induce (↑S) (simple_graph_clique_four_bridge_clique n)).Connected) (Classical.decPred _)] set v3 : Fin n := ⟨3,by omega⟩ with hv3 set v4 : Fin n := ⟨4,by omega⟩ with hv4 have hv3val : v3.val = 3 := rfl have hv4val : v4.val = 4 := rfl have hv34 : v3 ≠ v4 := by intro he; have := congrArg Fin.val he; omega set L : Finset (Fin n) := Finset.univ.filter (fun x : Fin n => x.val ≤ 3) with hL set R : Finset (Fin n) := Finset.univ.filter (fun x : Fin n => 4 ≤ x.val) with hR set F1 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => S.Nonempty ∧ ∀ x ∈ S, x.val ≤ 3) with hF1 set F2 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => S.Nonempty ∧ ∀ x ∈ S, 4 ≤ x.val) with hF2 set F3 : Finset (Finset (Fin n)) := Finset.univ.filter (fun S : Finset (Fin n) => v3 ∈ S ∧ v4 ∈ S) with hF3 have hT : Finset.univ.filter (fun S : Finset (Fin n) => (SimpleGraph.induce (↑S) (simple_graph_clique_four_bridge_clique n)).Connected) = F1 ∪ (F2 ∪ F3) := by rw [hF1,hF2,hF3,← Finset.filter_or,← Finset.filter_or] exact Finset.filter_congr (fun S _ => in148_connected_iff n v3 v4 hv3val hv4val S) have hd23 : Disjoint F2 F3 := by apply Finset.disjoint_left.mpr intro S hS hS' simp only [hF2,hF3,Finset.mem_filter,Finset.mem_univ,true_and] at hS hS' have := hS.2 v3 hS'.1 omega have hd1 : Disjoint F1 (F2 ∪ F3) := by apply Finset.disjoint_left.mpr intro S hS hS' simp only [hF1,Finset.mem_filter,Finset.mem_univ,true_and] at hS rcases Finset.mem_union.mp hS' with hS' | hS' · simp only [hF2,Finset.mem_filter,Finset.mem_univ,true_and] at hS' obtain ⟨x,hx⟩ := hS.1 have := hS.2 x hx have := hS'.2 x hx omega · simp only [hF3,Finset.mem_filter,Finset.mem_univ,true_and] at hS' have := hS.2 v4 hS'.2 omega have hF1eq : F1 = L.powerset.filter Finset.Nonempty := by rw [hF1,hL] ext S simp only [Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_powerset,Finset.subset_iff] exact ⟨fun h => ⟨h.2,h.1⟩,fun h => ⟨h.2,h.1⟩⟩ have hF2eq : F2 = R.powerset.filter Finset.Nonempty := by rw [hF2,hR] ext S simp only [Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_powerset,Finset.subset_iff] exact ⟨fun h => ⟨h.2,h.1⟩,fun h => ⟨h.2,h.1⟩⟩ have hLc : L.card = 4 := by rw [hL]; exact in148_card_filter_val_le_three n (by omega) have hRc : R.card = n-4 := by rw [hR] exact simple_graph_clique_four_glued_clique_connected_card_and_sum_card_filter_val_ge_four n (by omega) have hF1c : F1.card = 15 := by rw [hF1eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset,hLc] norm_num have hF1s : ∑ S ∈ F1, S.card = 32 := by rw [hF1eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset,hLc] norm_num have hF2c : F2.card = 2^(n-4)-1 := by rw [hF2eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_card_nonempty_powerset,hRc] have hF2s : ∑ S ∈ F2, S.card = (n-4)*2^(n-5) := by rw [hF2eq,simple_graph_clique_four_glued_clique_connected_card_and_sum_sum_card_nonempty_powerset,hRc] rw [show n-4-1 = n-5 by omega] have hF3c : F3.card = 2^(n-2) := by simpa only [Fintype.card_fin] using (in148_pair_card_sum v3 v4 hv34).1 have hF3s : ∑ S ∈ F3, S.card = (n-2)*2^(n-3)+2*2^(n-2) := by simpa only [Fintype.card_fin] using (in148_pair_card_sum v3 v4 hv34).2 constructor · rw [hT,Finset.card_union_of_disjoint hd1,Finset.card_union_of_disjoint hd23,hF1c,hF2c,hF3c] have hp : 2^(n-2) = 4*2^(n-4) := by rw [show n-2 = (n-4)+2 by omega,pow_add] norm_num ring rw [hp] have hpos : 1 ≤ 2^(n-4) := Nat.one_le_two_pow omega · rw [hT,Finset.sum_union hd1,Finset.sum_union hd23,hF1s,hF2s,hF3s] have hp2 : 2^(n-2) = 8*2^(n-5) := by rw [show n-2 = (n-5)+3 by omega,pow_add] norm_num ring have hp3 : 2^(n-3) = 4*2^(n-5) := by rw [show n-3 = (n-5)+2 by omega,pow_add] norm_num ring rw [hp2,hp3,show n-4 = (n-5)+1 by omega,show n-2 = (n-5)+3 by omega, show n+24 = (n-5)+29 by omega] ring