AFTD Auto-Formalizing Theoretical Domains

simple_graph_clique_four_bridge_clique_connected_card_and_sum

theoremverified

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

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

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

    lines 3–16

    uses Nat.le_of_lt_succ, Finset.card_image_of_injective, Fin.ext

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

    lines 22–36

    uses Finset.insert_erase

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

    lines 42–57

    uses Finset.erase_insert

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

    lines 64–101

    uses simple_graph_clique_four_glued_clique_connected_card_and_sum_sgc_reachable_mem_of_closed

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

    lines 102–138

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

    lines 144–166

    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_sub

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

    lines 177–198

    uses Finset.filter_congr_decidable, Finset.filter_or, Finset.filter_congr, in148_connected_iff

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

    lines 199–217

    uses Finset.disjoint_left, Finset.mem_union

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

    lines 218–246

    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_sum

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

    lines 247–255

    uses Finset.card_union_of_disjoint, pow_add, Nat.one_le_two_pow

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

    lines 256–267

    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.

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

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