AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_eq_avg_of_isolated

theoremverified

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

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.

  1. 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.

    line 5

    uses SimpleGraph.degree_eq_zero

      have hiso : G.IsIsolated v := (SimpleGraph.degree_eq_zero G v).1 hv
  2. The 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.

    lines 6–18

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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
  3. 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.

    line 19

      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

/-- 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]
See it in the graphDiscuss this resultChallenge it