dominating_average_star_like_vertex_stability_of_card_two
For every finite simple graph G on 2 vertices with no isolated vertex, the stability inequality 5 d_*(G) ≤ 51 (2·2/3 - avd(G)) holds.
Statement
theorem dominating_average_star_like_vertex_stability_of_card_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 2) (hiso : ∀ w, 0 < G.degree w) : 5 * (simple_graph_star_like_deletion_number G : ℚ) ≤ 51 * (2 * (Fintype.card V : ℚ) / 3 - simple_graph_avg_dominating_order G)
- Related work
- arXiv:2208.10475v2: The average size of a dominating set in a graph
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_star_like_deletion_numberThe star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced…
- 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_is_star_like_complete_twoK₂ is star-like.
- simple_graph_is_star_likeG is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.
- 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.
Read back from the Lean
For any finite type V with decidable equality and any simple graph G on V with decidable adjacency, if the cardinality of V is 2 and every vertex of G has degree strictly greater than 0, then 5 times the star-like deletion number of G is less than or equal to 51 times (2 * |V| / 3 - the average dominating order of G), where the operations and inequality are in the rational numbers ℚ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
For a graph G on 2 vertices with no isolated vertex, every vertex must be adjacent to the other, so G is the complete graph K_2. Since both vertices have degree 1, K_2 is already star-like, meaning its star-like deletion number is d_*(G) = 0. The dominating sets of K_2 are the 3 non-empty subsets of vertices, whose sizes sum to 4, yielding an average dominating set order avd(G) = 4/3. Substituting these values into the stability inequality gives 0 ≤ 0, which holds with equality.
Any two distinct vertices a, b in a 2-element set V form the universal set {a, b} = Finset.univ.
Since a ≠ b, the two-element set {a, b} has cardinality 2. Because |V| = 2, any subset of V with cardinality 2 is the whole universe.
uses
Finset.eq_univ_of_cardhave h2 : ({a, b} : Finset V).card = 2 := by simp [hab] exact (Finset.eq_univ_of_card _ (by rw [h2, hV])).symm
The graph G is complete: every pair of distinct vertices x ≠ y is adjacent.
Because G has no isolated vertex, x has positive degree and hence an adjacent neighbor w. In a simple graph, w ≠ x. By the universe pair lemma, w must be in {x, y}, leaving w = y as the only possibility. Thus x and y are adjacent.
uses
SimpleGraph.degree_pos_iff_exists_adj,dominating_average_star_like_vertex_stability_of_card_two_univ_pair,Finset.mem_univ,Finset.mem_insert,Finset.mem_singletonintro x y hxy obtain ⟨w, hw⟩ := (SimpleGraph.degree_pos_iff_exists_adj G x).mp (hiso x) have hwne : w ≠ x := (G.ne_of_adj hw).symm have hmem : w ∈ ({x, y} : Finset V) := by rw [← dominating_average_star_like_vertex_stability_of_card_two_univ_pair hV x y hxy] exact Finset.mem_univ w rw [Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with h | h · exact absurd h hwne · rw [h] at hw exact hw
Every complete graph H on 2 vertices is star-like.
In a complete graph on 2 vertices, the neighborhood of any vertex w consists of all other vertices, which is W \ {w}. Its cardinality is 2 - 1 = 1, so every vertex has degree 1. Graphs where all vertices have degree 1 satisfy the definition of star-like.
uses
SimpleGraph.neighborFinset_eq_filter,Finset.mem_filter,Finset.mem_erase,SimpleGraph.degree,Finset.card_erase_of_mem,Finset.card_univintro w left have hneigh : H.neighborFinset w = (Finset.univ : Finset W).erase w := by ext u rw [SimpleGraph.neighborFinset_eq_filter, Finset.mem_filter, Finset.mem_erase] constructor · rintro ⟨-, h⟩ exact ⟨(H.ne_of_adj h).symm, Finset.mem_univ u⟩ · rintro ⟨hne, -⟩ exact ⟨Finset.mem_univ u, hcomp w u (fun huw => hne huw.symm)⟩ rw [SimpleGraph.degree, hneigh, Finset.card_erase_of_mem (Finset.mem_univ w), Finset.card_univ, hcard]
The star-like deletion number of G is 0.
The deletion number d_*(G) is the minimum size of a subset X whose deletion leaves a star-like induced subgraph. Deleting X = ∅ leaves all 2 vertices, which induce a complete graph on 2 vertices and thus a star-like graph. Hence 0 is achieved.
uses
dominating_average_star_like_vertex_stability_of_card_two_complete,Nat.sInf_eq_zero,dominating_average_star_like_vertex_stability_of_card_two_star,Subtype.exthave hcomp := dominating_average_star_like_vertex_stability_of_card_two_complete hV G hiso rw [simple_graph_star_like_deletion_number, Nat.sInf_eq_zero] left refine ⟨∅, ?_, rfl⟩ have hcardW : Fintype.card {v : V // v ∈ ((↑(∅ : Finset V)) : Set V)ᶜ} = 2 := by simpa using hV exact dominating_average_star_like_vertex_stability_of_card_two_star (H := SimpleGraph.induce ((↑(∅ : Finset V))ᶜ) G) hcardW (fun a b hab => hcomp a.val b.val (fun h => hab (Subtype.ext h)))
The sum of the sizes of all subsets of a 2-element set is 4. automation
Grouping subsets by size, the sum of cardinalities is ∑_{k=0}^2 (2 choose k) * k = 0 + 2 + 2 = 4, which is verified by direct finite computation.
uses
Finset.sum_powerset_apply_card,Finset.powerset_univ,Finset.card_univhave h2 : ((∑ S ∈ (Finset.univ : Finset (Finset V)), S.card : ℕ) : ℚ) = 4 := by have h := Finset.sum_powerset_apply_card (fun n : ℕ => n) (x := (Finset.univ : Finset V)) rw [← Finset.powerset_univ (α := V), h] simp only [Finset.card_univ, hV] decide simpa using h2
In a complete graph, every dominating set is non-empty.
If the empty set were dominating, every vertex would be in ∅ or adjacent to a vertex in ∅, which is impossible for any element of the non-empty vertex set V.
uses
Finset.not_nonempty_iff_eq_empty,Finset.mem_filter,Finset.mem_univ,Classical.arbitraryconstructor · rintro h by_contra h0 rw [Finset.not_nonempty_iff_eq_empty] at h0 have key : (∅ : Finset V) ∈ simple_graph_dominating_sets G := h0 ▸ h simp only [simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] at key have := key (Classical.arbitrary V) simp at this
In a complete graph, every non-empty set of vertices is a dominating set.
Given any vertex w, if w is in S it is dominated. If w is not in S, choosing any u in S gives u ≠ w, and completeness of the graph implies u is adjacent to w, so w is again dominated.
uses
Finset.mem_filter,Finset.mem_univ· intro h simp only [simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] intro w obtain ⟨u, hu⟩ := h by_cases hw : w ∈ S · exact Or.inl hw · exact Or.inr ⟨u, hu, hcomp u w (fun huw => hw (huw ▸ hu))⟩
The dominating sets of G are precisely the non-empty subsets of V.
Since |V| = 2, V is non-empty. Because G is complete, dominating sets are characterized as exactly the non-empty subsets of V, or equivalently the powerset minus the empty set.
uses
Fintype.card_pos_iff.mp,dominating_average_star_like_vertex_stability_of_card_two_complete,dominating_average_star_like_vertex_stability_of_card_two_dom_iff,Finset.mem_erase,Finset.nonempty_iff_ne_emptyhave hne : Nonempty V := Fintype.card_pos_iff.mp (by rw [hV]; norm_num) haveI := hne have hcomp := dominating_average_star_like_vertex_stability_of_card_two_complete hV G hiso have hdom : simple_graph_dominating_sets G = (Finset.univ : Finset (Finset V)).erase ∅ := by ext S rw [dominating_average_star_like_vertex_stability_of_card_two_dom_iff G hcomp S, Finset.mem_erase, Finset.nonempty_iff_ne_empty] simp
The average order of dominating sets in G is avd(G) = 4/3. automation
The sum of sizes of dominating sets equals the sum over all subsets minus the size of ∅, giving 4 - 0 = 4. The number of dominating sets is 2^2 - 1 = 3. Dividing the sum of sizes by the count gives 4/3.
uses
Finset.sum_erase,dominating_average_star_like_vertex_stability_of_card_two_sum_univ,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univ,Fintype.card_finsethave hsum : (∑ S ∈ simple_graph_dominating_sets G, (S.card : ℚ)) = 4 := by rw [hdom, Finset.sum_erase (s := (Finset.univ : Finset (Finset V))) (f := fun S => (S.card : ℚ)) (a := (∅ : Finset V)) (by simp)] exact dominating_average_star_like_vertex_stability_of_card_two_sum_univ hV have hcard : (simple_graph_dominating_sets G).card = 3 := by rw [hdom, Finset.card_erase_of_mem (Finset.mem_univ (∅ : Finset V)), Finset.card_univ, Fintype.card_finset, hV] norm_num rw [simple_graph_avg_dominating_order, hsum, hcard] norm_num
The stability inequality 5 d_*(G) ≤ 51 (2|V|/3 - avd(G)) holds. automation
Substituting |V| = 2, d_*(G) = 0, and avd(G) = 4/3, the left-hand side is 5 * 0 = 0 and the right-hand side is 51 * (4/3 - 4/3) = 0. The inequality 0 ≤ 0 is verified by arithmetic.
uses
dominating_average_star_like_vertex_stability_of_card_two_del,dominating_average_star_like_vertex_stability_of_card_two_avdrw [dominating_average_star_like_vertex_stability_of_card_two_del hcard G hiso, dominating_average_star_like_vertex_stability_of_card_two_avd hcard G hiso, hcard] norm_num
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the whole type is the universal set.
SimpleGraph.degree_pos_iff_exists_adj- A vertex has positive degree if and only if there exists a vertex adjacent to it.
dominating_average_star_like_vertex_stability_of_card_two_univ_pair- Any pair of distinct elements in a 2-element type exhausts the entire universe.
Finset.mem_univ- Every element of a finite type is in the universal finset.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
SimpleGraph.neighborFinset_eq_filter- The neighbor set of a vertex is the filter of all vertices adjacent to it.
Finset.mem_filter- An element belongs to a filtered finset if and only if it is in the finset and satisfies the predicate.
Finset.mem_erase- An element belongs to s.erase b if and only if it is not b and belongs to s.
SimpleGraph.degree- The degree of a vertex is the cardinality of its neighbor finset.
Finset.card_erase_of_mem- Erasing an element from a finset decreases its cardinality by 1.
Finset.card_univ- The cardinality of the universal finset equals the cardinality of the underlying finite type.
dominating_average_star_like_vertex_stability_of_card_two_complete- Every finite simple graph on 2 vertices with no isolated vertices is complete.
Nat.sInf_eq_zero- The infimum of a set of natural numbers is 0 if and only if 0 belongs to the set or the set is empty.
dominating_average_star_like_vertex_stability_of_card_two_star- Any complete graph on 2 vertices is star-like.
Subtype.ext- Subtype elements are equal if and only if their underlying values are equal.
Finset.sum_powerset_apply_card- The sum of a function of subset cardinalities over the powerset can be evaluated by grouping subsets by size.
Finset.powerset_univ- The powerset of the universal finset is the universal finset of finsets.
Finset.not_nonempty_iff_eq_empty- A finset is not non-empty if and only if it is empty.
Classical.arbitrary- Chooses an arbitrary element from a non-empty type.
Fintype.card_pos_iff.mp- A finite type with strictly positive cardinality is non-empty.
dominating_average_star_like_vertex_stability_of_card_two_dom_iff- In a complete graph on a non-empty vertex set, a subset is dominating if and only if it is non-empty.
Finset.nonempty_iff_ne_empty- A finset is non-empty if and only if it is not empty.
Finset.sum_erase- If a function takes value 0 at element a, the sum over s.erase a equals the sum over s.
dominating_average_star_like_vertex_stability_of_card_two_sum_univ- The sum of the sizes of all subsets of a 2-element type is 4.
Fintype.card_finset- The number of subsets of a finite type of cardinality n is 2^n.
dominating_average_star_like_vertex_stability_of_card_two_del- The star-like deletion number of a 2-vertex graph with no isolated vertices is 0.
dominating_average_star_like_vertex_stability_of_card_two_avd- The average dominating set size of a 2-vertex graph with no isolated vertices is 4/3.
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.
private lemma dominating_average_star_like_vertex_stability_of_card_two_univ_pair {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V = 2) (a b : V) (hab : a ≠ b) : (Finset.univ : Finset V) = {a, b} := by have h2 : ({a, b} : Finset V).card = 2 := by simp [hab] exact (Finset.eq_univ_of_card _ (by rw [h2, hV])).symmprivate lemma dominating_average_star_like_vertex_stability_of_card_two_complete {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V = 2) (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w) : ∀ x y : V, x ≠ y → G.Adj x y := by intro x y hxy obtain ⟨w, hw⟩ := (SimpleGraph.degree_pos_iff_exists_adj G x).mp (hiso x) have hwne : w ≠ x := (G.ne_of_adj hw).symm have hmem : w ∈ ({x, y} : Finset V) := by rw [← dominating_average_star_like_vertex_stability_of_card_two_univ_pair hV x y hxy] exact Finset.mem_univ w rw [Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with h | h · exact absurd h hwne · rw [h] at hw exact hwprivate lemma dominating_average_star_like_vertex_stability_of_card_two_star {W : Type*} [Fintype W] [DecidableEq W] (H : SimpleGraph W) [DecidableRel H.Adj] (hcard : Fintype.card W = 2) (hcomp : ∀ a b, a ≠ b → H.Adj a b) : simple_graph_is_star_like H := by intro w left have hneigh : H.neighborFinset w = (Finset.univ : Finset W).erase w := by ext u rw [SimpleGraph.neighborFinset_eq_filter, Finset.mem_filter, Finset.mem_erase] constructor · rintro ⟨-, h⟩ exact ⟨(H.ne_of_adj h).symm, Finset.mem_univ u⟩ · rintro ⟨hne, -⟩ exact ⟨Finset.mem_univ u, hcomp w u (fun huw => hne huw.symm)⟩ rw [SimpleGraph.degree, hneigh, Finset.card_erase_of_mem (Finset.mem_univ w), Finset.card_univ, hcard]private lemma dominating_average_star_like_vertex_stability_of_card_two_del {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V = 2) (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w) : simple_graph_star_like_deletion_number G = 0 := by have hcomp := dominating_average_star_like_vertex_stability_of_card_two_complete hV G hiso rw [simple_graph_star_like_deletion_number, Nat.sInf_eq_zero] left refine ⟨∅, ?_, rfl⟩ have hcardW : Fintype.card {v : V // v ∈ ((↑(∅ : Finset V)) : Set V)ᶜ} = 2 := by simpa using hV exact dominating_average_star_like_vertex_stability_of_card_two_star (H := SimpleGraph.induce ((↑(∅ : Finset V))ᶜ) G) hcardW (fun a b hab => hcomp a.val b.val (fun h => hab (Subtype.ext h)))private lemma dominating_average_star_like_vertex_stability_of_card_two_sum_univ {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V = 2) : (∑ S ∈ (Finset.univ : Finset (Finset V)), (S.card : ℚ)) = 4 := by have h2 : ((∑ S ∈ (Finset.univ : Finset (Finset V)), S.card : ℕ) : ℚ) = 4 := by have h := Finset.sum_powerset_apply_card (fun n : ℕ => n) (x := (Finset.univ : Finset V)) rw [← Finset.powerset_univ (α := V), h] simp only [Finset.card_univ, hV] decide simpa using h2private lemma dominating_average_star_like_vertex_stability_of_card_two_dom_iff {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcomp : ∀ x y : V, x ≠ y → G.Adj x y) (S : Finset V) : S ∈ simple_graph_dominating_sets G ↔ S.Nonempty := by constructor · rintro h by_contra h0 rw [Finset.not_nonempty_iff_eq_empty] at h0 have key : (∅ : Finset V) ∈ simple_graph_dominating_sets G := h0 ▸ h simp only [simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] at key have := key (Classical.arbitrary V) simp at this · intro h simp only [simple_graph_dominating_sets, Finset.mem_filter, Finset.mem_univ, true_and] intro w obtain ⟨u, hu⟩ := h by_cases hw : w ∈ S · exact Or.inl hw · exact Or.inr ⟨u, hu, hcomp u w (fun huw => hw (huw ▸ hu))⟩private lemma dominating_average_star_like_vertex_stability_of_card_two_avd {V : Type*} [Fintype V] [DecidableEq V] (hV : Fintype.card V = 2) (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w) : simple_graph_avg_dominating_order G = 4 / 3 := by have hne : Nonempty V := Fintype.card_pos_iff.mp (by rw [hV]; norm_num) haveI := hne have hcomp := dominating_average_star_like_vertex_stability_of_card_two_complete hV G hiso have hdom : simple_graph_dominating_sets G = (Finset.univ : Finset (Finset V)).erase ∅ := by ext S rw [dominating_average_star_like_vertex_stability_of_card_two_dom_iff G hcomp S, Finset.mem_erase, Finset.nonempty_iff_ne_empty] simp have hsum : (∑ S ∈ simple_graph_dominating_sets G, (S.card : ℚ)) = 4 := by rw [hdom, Finset.sum_erase (s := (Finset.univ : Finset (Finset V))) (f := fun S => (S.card : ℚ)) (a := (∅ : Finset V)) (by simp)] exact dominating_average_star_like_vertex_stability_of_card_two_sum_univ hV have hcard : (simple_graph_dominating_sets G).card = 3 := by rw [hdom, Finset.card_erase_of_mem (Finset.mem_univ (∅ : Finset V)), Finset.card_univ, Fintype.card_finset, hV] norm_num rw [simple_graph_avg_dominating_order, hsum, hcard] norm_num/-- The stability inequality holds at order n = 2. -/theorem dominating_average_star_like_vertex_stability_of_card_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 2) (hiso : ∀ w, 0 < G.degree w) : 5 * (simple_graph_star_like_deletion_number G : ℚ) ≤ 51 * (2 * (Fintype.card V : ℚ) / 3 - simple_graph_avg_dominating_order G) := by rw [dominating_average_star_like_vertex_stability_of_card_two_del hcard G hiso, dominating_average_star_like_vertex_stability_of_card_two_avd hcard G hiso, hcard] norm_num