AFTD Auto-Formalizing Theoretical Domains

simple_graph_avg_dominating_order_deficit_bridge

theoremverified

The dominating set order deficit 2n/3 - avd(G) can be rewritten as (2n|D(G)| - 3 ∑_{S∈D(G)} |S|) / (3|D(G)|).

Statement

theorem simple_graph_avg_dominating_order_deficit_bridge {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : 2 * (Fintype.card V : ℚ) / 3 - simple_graph_avg_dominating_order G = (2 * (Fintype.card V : ℚ) * (simple_graph_dominating_sets G).card - 3 * (∑ S ∈ simple_graph_dominating_sets G, (S.card : ℚ))) / (3 * (simple_graph_dominating_sets G).card)
Source
step towards dominating_average_star_like_vertex_stability
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_avg_dominating_orderavd(G): the global average order of dominating sets of G, i.e. the average size of all dominating sets of G. This is the quantity of…
  • simple_graph_dominating_setsD(G): the dominating sets of G, i.e. the finite vertex sets S such that every vertex of G lies in S or is adjacent to a vertex of S.

Lean source view module on GitHub

/-- The average dominating set order deficit 2n/3 - avd(G) expressed as an exact rational fraction over 3|D(G)|. -/
theorem simple_graph_avg_dominating_order_deficit_bridge {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : 2 * (Fintype.card V : ℚ) / 3 - simple_graph_avg_dominating_order G = (2 * (Fintype.card V : ℚ) * (simple_graph_dominating_sets G).card - 3 * (∑ S ∈ simple_graph_dominating_sets G, (S.card : ℚ))) / (3 * (simple_graph_dominating_sets G).card) := by
  have hne : (simple_graph_dominating_sets G).Nonempty := ⟨Finset.univ, by
    rw [simple_graph_dominating_sets, Finset.mem_filter]
    exact ⟨Finset.mem_univ _, fun w => Or.inl (Finset.mem_univ w)⟩⟩
  have hd : ((simple_graph_dominating_sets G).card : ℚ) ≠ 0 := by
    have : 0 < (simple_graph_dominating_sets G).card := Finset.card_pos.mpr hne
    positivity
  unfold simple_graph_avg_dominating_order
  field_simp
See it in the graphDiscuss this resultChallenge it