simple_graph_avg_connected_induced_order_clique_four_glued_clique
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
- simple_graph_avg_connected_induced_orderA(G) = (Σ |S|)/N, the sum over the N vertex sets S ⊆ V(G) whose induced subgraph G[S] is connected (and nonempty).
- simple_graph_clique_four_glued_cliqueThe graph on {0,…,n−1} formed by a clique on {0,1,2,3} and a clique on {3,…,n−1}, sharing the vertex 3.
- 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)…
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.
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.
uses
Finset.mem_filterext x simp only [Finset.mem_filter]
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$.
uses
simple_graph_clique_four_glued_clique_connected_card_and_sumobtain ⟨h1, h2⟩ := simple_graph_clique_four_glued_clique_connected_card_and_sum n hnThe 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$.
uses
simple_graph_avg_connected_induced_order,simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congrsimp 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 _)]
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.
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.
- In Lean, `Finset.filter` carries a typeclass parameter for the decidability of the predicate. The definition `simple_graph_avg_connected_induced_order` synthesizes its own classical instance, whereas the counting theorem `simple_graph_clique_four_glued_clique_connected_card_and_sum` uses `Classical.dec _`. Although the resulting sets are mathematically identical, Lean's syntactic rewrite `rw` requires the helper lemma `simple_graph_avg_connected_induced_order_clique_four_glued_clique_filter_congr` to unify the instances before the substitutions can take place.
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.
/-- 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]