simple_graph_local_avg_dominating_order_eq_avg_of_isolated
If v is an isolated vertex of G (deg v = 0), then avd_v(G) = avd(G): every dominating set contains v, so the dominating sets containing v are exactly all dominating sets. This is what reduces the local statement for a graph 'with no isolated vertex except possibly v' to the global one.
Statement
theorem simple_graph_local_avg_dominating_order_eq_avg_of_isolated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (hv : G.degree v = 0) : simple_graph_local_avg_dominating_order G v = simple_graph_avg_dominating_order G
- Source
- step towards simple_graph_local_avg_dominating_order_stem_le
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- simple_graph_local_avg_dominating_orderavd_v(G): the local average order of dominating sets containing v, i.e. the average size of the dominating sets of G that contain v.
- simple_graph_dominating_sets_containingD_v(G): the dominating sets of G that contain v, where S dominates G when every vertex is in S or adjacent to a vertex of S.
The proof, explained
The proof shows that for an isolated vertex v (degree 0), the local average size of dominating sets containing v coincides with the global average dominating set size of G. Because v has no neighbors, no other vertex can dominate v, so every dominating set of G must contain v. Consequently, the dominating sets containing v are exactly all dominating sets of G. Substituting this set equality into the definition of the local average immediately reduces it to the global average.
The vertex v is isolated in G.
By hypothesis `hv`, the degree of v is 0. The equivalence `SimpleGraph.degree_eq_zero` therefore establishes that v is isolated (`G.IsIsolated v`), having no adjacent vertices in G.
uses
SimpleGraph.degree_eq_zerohave hiso : G.IsIsolated v := (SimpleGraph.degree_eq_zero G v).1 hvThe dominating sets containing v are precisely all dominating sets of G.
To prove the set equality `hset`, we apply extensionality (`ext S`) to show that an arbitrary subset S ⊆ V belongs to the dominating sets containing v if and only if it belongs to all dominating sets. Unfolding the definitions and simplifying membership using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, this reduces to showing that (v ∈ S ∧ S dominates G) ↔ S dominates G. The forward implication is immediate. For the reverse implication, suppose S dominates G. By definition, S must dominate v, which means either v ∈ S or there exists u ∈ S adjacent to v. Since v is isolated (`hiso`), it has no neighbors, so the adjacency case is impossible. Thus v ∈ S must hold, completing the equality.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hset : simple_graph_dominating_sets_containing G v = simple_graph_dominating_sets G := by ext S simp only [simple_graph_dominating_sets_containing, simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨hvS, hdom⟩ exact hdom · intro hdom refine ⟨?_, hdom⟩ rcases hdom v with hvS | ⟨u, hu, hadj⟩ · exact hvS · exfalso exact hiso u hadj.symm
The local average dominating order at v equals the global average dominating order of G.
Unfolding the definitions of `simple_graph_local_avg_dominating_order` and `simple_graph_avg_dominating_order` and rewriting using the equality `hset`, the summation over dominating sets containing v and the count of such sets are replaced by the corresponding global sums and counts, making the local and global averages identical.
simp only [simple_graph_local_avg_dominating_order, simple_graph_avg_dominating_order, hset]
SimpleGraph.degree_eq_zero- A vertex in a graph has degree zero if and only if it is isolated (has no neighbors).
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the ambient finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- A conjunction `True ∧ p` simplifies to `p`.
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.
/-- For an isolated vertex v every dominating set already contains v, so the local and global averages coincide. This is the identity that turns the isolated-vertex case of any local statement into a global one. -/theorem simple_graph_local_avg_dominating_order_eq_avg_of_isolated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (hv : G.degree v = 0) : simple_graph_local_avg_dominating_order G v = simple_graph_avg_dominating_order G := by have hiso : G.IsIsolated v := (SimpleGraph.degree_eq_zero G v).1 hv have hset : simple_graph_dominating_sets_containing G v = simple_graph_dominating_sets G := by ext S simp only [simple_graph_dominating_sets_containing, simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨hvS, hdom⟩ exact hdom · intro hdom refine ⟨?_, hdom⟩ rcases hdom v with hvS | ⟨u, hu, hadj⟩ · exact hvS · exfalso exact hiso u hadj.symm simp only [simple_graph_local_avg_dominating_order, simple_graph_avg_dominating_order, hset]