simple_graph_avg_connected_induced_order
def
A(G) = (Σ |S|)/N, the sum over the N vertex sets S ⊆ V(G) whose induced subgraph G[S] is connected (and nonempty).
Statement
noncomputable def simple_graph_avg_connected_induced_order {V : Type*} [Fintype V] (G : SimpleGraph V) : ℚ
- Defined in
- arXiv:2610.27553 (A proof of Vince's conjecture on the average order of connected induced subgraphs), Sec. 1, definition of A(G)
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 1
- simple_graph_avg_connected_induced_order_clique_four_glued_cliqueFor 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…
Lean source view module on GitHub
/-- A(G): the average order of the connected induced subgraphs of G, i.e. the mean of |S| over the vertex sets S inducing a connected subgraph (connected includes nonempty). -/ noncomputable def simple_graph_avg_connected_induced_order {V : Type*} [Fintype V] (G : SimpleGraph V) : ℚ := by classical exact (((Finset.univ.filter (fun S : Finset V => (G.induce (S : Set V)).Connected)).sum Finset.card : ℕ) : ℚ) / (Finset.univ.filter (fun S : Finset V => (G.induce (S : Set V)).Connected)).card