AFTD Auto-Formalizing Theoretical Domains

dominating_average_star_like_vertex_stability_of_card_two

theoremverifiedoriginal

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

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.

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

    lines 4–5

    uses Finset.eq_univ_of_card

      have h2 : ({a, b} : Finset V).card = 2 := by simp [hab]
      exact (Finset.eq_univ_of_card _ (by rw [h2, hV])).symm
  2. 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.

    lines 11–21

    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_singleton

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

    lines 27–38

    uses SimpleGraph.neighborFinset_eq_filter, Finset.mem_filter, Finset.mem_erase, SimpleGraph.degree, Finset.card_erase_of_mem, Finset.card_univ

      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]
  4. 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.

    lines 44–52

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

      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)))
  5. 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.

    lines 57–62

    uses Finset.sum_powerset_apply_card, Finset.powerset_univ, Finset.card_univ

      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 h2
  6. 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.

    lines 69–77

    uses Finset.not_nonempty_iff_eq_empty, Finset.mem_filter, Finset.mem_univ, Classical.arbitrary

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

    lines 78–84

    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))⟩
  8. 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.

    lines 90–97

    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_empty

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

    lines 98–107

    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_finset

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

    lines 115–117

    uses dominating_average_star_like_vertex_stability_of_card_two_del, dominating_average_star_like_vertex_stability_of_card_two_avd

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

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