AFTD Auto-Formalizing Theoretical Domains

simple_graph_avg_connected_induced_order_clique_four_glued_clique

theoremverified

For n ≥ 7, A(K_4 ·_v K_{n−3}) = (12 + (n−4)2^{n−5} + 2^{n−1} + (n−1)2^{n−2}) / (2^{n−4} + 2^{n−1} + 6): the connected vertex sets are the nonempty subsets of one clique minus the shared vertex, and all sets containing the shared vertex.

Statement

theorem simple_graph_avg_connected_induced_order_clique_four_glued_clique (n : ℕ) (hn : 7 ≤ n) :
    simple_graph_avg_connected_induced_order (simple_graph_clique_four_glued_clique n) =
      ((12 + (n - 4) * 2 ^ (n - 5) + 2 ^ (n - 1) + (n - 1) * 2 ^ (n - 2) : ℕ) : ℚ) /
        ((2 ^ (n - 4) + 2 ^ (n - 1) + 6 : ℕ) : ℚ)
Source
evaluation of A(G) on the conjectured extremal graph of OP-444; serves simple_graph_avg_connected_induced_order_min_cut_vertex_no_bridge
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The average order of a connected induced subgraph is defined as the sum of the vertex counts of all connected induced subgraphs divided by their total count. For the glued clique graph $K_4 \cdot_v K_{n-3}$ with $n \ge 7$, a previous classification theorem determines both the total number of connected induced subgraphs and the sum of their vertex counts. The proof unfolds the definition of average order, aligns the decidability instances of the filtered sets using a congruence helper lemma, and substitutes the known sum and count into the numerator and denominator.

  1. Filtering a finite set by a predicate is independent of the choice of decidability instance.

    By finset extensionality (`ext x`), two filtered sets are equal if they contain the same elements. By `Finset.mem_filter`, membership in a filtered set requires only membership in the base set and satisfaction of the predicate, which does not depend on the decidability instance.

    lines 5–6

    uses Finset.mem_filter

      ext x
      simp only [Finset.mem_filter]
  2. The number of connected induced subgraphs is $2^{n-4} + 2^{n-1} + 6$, and the sum of their vertex counts is $12 + (n-4)2^{n-5} + 2^{n-1} + (n-1)2^{n-2}$.

    We invoke the classification theorem `simple_graph_clique_four_glued_clique_connected_card_and_sum` with $7 \le n$, which provides the count of connected induced subgraphs as hypothesis $h_1$ and the sum of their vertex counts as hypothesis $h_2$.

    line 12

    uses simple_graph_clique_four_glued_clique_connected_card_and_sum

      obtain ⟨h1, h2⟩ := simple_graph_clique_four_glued_clique_connected_card_and_sum n hn
  3. The average order is expressed as the sum of vertex counts over the total count of connected induced subgraphs, with decidability instances aligned to match the counting lemma.

    Unfolding `simple_graph_avg_connected_induced_order` rewrites the goal into the quotient of the sum of orders by the total number of connected induced subgraphs. Then `simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr` replaces the synthesized decidability instance in both filtered sets with `Classical.dec`, matching the instances in hypotheses $h_1$ and $h_2$.

    lines 13–17

    uses simple_graph_avg_connected_induced_order, simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr

      simp only [simple_graph_avg_connected_induced_order]
      rw [simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr
        (fun S : Finset (Fin n) =>
          (SimpleGraph.induce (S : Set (Fin n)) (simple_graph_clique_four_glued_clique n)).Connected)
        _ (fun x => Classical.dec _)]
  4. The average connected induced order equals $((12 + (n-4)2^{n-5} + 2^{n-1} + (n-1)2^{n-2}) : ℚ) / ((2^{n-4} + 2^{n-1} + 6) : ℚ)$.

    Rewriting with $h_2$ replaces the sum of orders in the numerator, and rewriting with $h_1$ replaces the total count in the denominator, completing the proof.

    line 18

      rw [h2, h1]
Finset.mem_filter
An element $a$ belongs to `Finset.filter p s` if and only if $a \in s$ and $p(a)$ holds.
simple_graph_clique_four_glued_clique_connected_card_and_sum
For $n \ge 7$, the glued clique graph $K_4 \cdot_v K_{n-3}$ has $2^{n-4} + 2^{n-1} + 6$ connected induced subgraphs, and the sum of their vertex counts is $12 + (n-4)2^{n-5} + 2^{n-1} + (n-1)2^{n-2}$.
simple_graph_avg_connected_induced_order
The average order of a connected induced subgraph in a finite graph $G$, defined as the sum of the vertex counts of all connected induced subgraphs divided by the total number of connected induced subgraphs.
simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr
Two filtered finite sets with the same underlying set and predicate are equal, regardless of the choice of decidability instance.

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

/-- Two `Finset.filter`s of the same predicate differ only in their decidability instance. -/theorem simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr    {α : Type*} (p : α → Prop) (h1 h2 : DecidablePred p) (s : Finset α) :    @Finset.filter α p h1 s = @Finset.filter α p h2 s := by  ext x  simp only [Finset.mem_filter]theorem simple_graph_avg_connected_induced_order_clique_four_glued_clique (n : ℕ) (hn : 7 ≤ n) :    simple_graph_avg_connected_induced_order (simple_graph_clique_four_glued_clique n) =      ((12 + (n - 4) * 2 ^ (n - 5) + 2 ^ (n - 1) + (n - 1) * 2 ^ (n - 2) : ℕ) : ℚ) /        ((2 ^ (n - 4) + 2 ^ (n - 1) + 6 : ℕ) : ℚ) := by  obtain ⟨h1, h2⟩ := simple_graph_clique_four_glued_clique_connected_card_and_sum n hn  simp only [simple_graph_avg_connected_induced_order]  rw [simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr    (fun S : Finset (Fin n) =>      (SimpleGraph.induce (S : Set (Fin n)) (simple_graph_clique_four_glued_clique n)).Connected)    _ (fun x => Classical.dec _)]  rw [h2, h1]
See it in the graphDiscuss this resultChallenge it