AFTD Auto-Formalizing Theoretical Domains

dominating_pair_of_card_le_two

theoremverified

In any graph with at most two vertices, the vertices themselves form a dominating set of size at most 2.

Statement

theorem dominating_pair_of_card_le_two {V : Type*} [Fintype V] (G : SimpleGraph V)
    [Nonempty V] (h : Fintype.card V ≤ 2) :
    ∃ u v : V, ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w
Source
step towards p7_claw_free_dominating_pair_of_no_hole
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof proceeds by case analysis on the cardinality of the vertex set V. When |V| ≤ 1, any chosen vertex u paired with itself dominates the graph because every vertex is equal to u. When |V| > 1, the hypothesis |V| ≤ 2 forces |V| = 2, so V consists of exactly two distinct vertices x and y, and the pair (x, y) covers all vertices directly by equality.

  1. Case distinction on whether |V| ≤ 1 or |V| > 1.

    Under classical logic, we split into two cases: either the vertex set V has at most one vertex, or it has strictly more than one.

    lines 5–6

      classical
      by_cases h1 : Fintype.card V ≤ 1
  2. If |V| ≤ 1, choosing any vertex u and setting the pair to (u, u) dominates the graph.

    Since V is nonempty, we pick an arbitrary vertex u ∈ V and propose the pair (u, u). For any vertex w ∈ V, the assumption |V| ≤ 1 implies w = u by Fintype.card_le_one_iff.mp. Hence the first disjunct w = u of the domination condition is satisfied.

    lines 7–10

    uses Fintype.card_le_one_iff.mp

      · obtain ⟨u⟩ := ‹Nonempty V›
        refine ⟨u, u, fun w => ?_⟩
        left
        exact Fintype.card_le_one_iff.mp h1 w u
  3. If |V| > 1, then |V| = 2, so the vertex set consists of two distinct vertices x and y.

    Since |V| ≤ 2 and ¬(|V| ≤ 1), linear arithmetic shows |V| = 2. It follows by Finset.card_univ that the universal finset of V has cardinality 2. Therefore, by Finset.card_eq_two.mp, there exist two distinct vertices x, y ∈ V such that the universal finset equals {x, y}.

    lines 11–14

    uses Finset.card_univ, Finset.card_eq_two.mp

      · have h2 : Fintype.card V = 2 := by omega
        have hc : (Finset.univ : Finset V).card = 2 := by
          rw [Finset.card_univ]; exact h2
        obtain ⟨x, y, hxy, hset⟩ := Finset.card_eq_two.mp hc
  4. The pair (x, y) dominates the graph.

    We choose (x, y) as the candidate pair. Every vertex w ∈ V belongs to the universal finset by Finset.mem_univ, which equals {x, y}. Unfolding set membership with Finset.mem_insert and Finset.mem_singleton shows w = x or w = y. In the first case, the disjunct w = x holds; in the second, w = y holds.

    lines 15–21

    uses Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton

        refine ⟨x, y, fun w => ?_⟩
        have hw : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w
        rw [hset] at hw
        simp only [Finset.mem_insert, Finset.mem_singleton] at hw
        rcases hw with rfl | rfl
        · left; rfl
        · right; left; rfl
Fintype.card_le_one_iff.mp
if a finite type has cardinality at most 1, then all of its elements are equal
Finset.card_univ
the cardinality of the universal finset of a finite type equals the cardinality of the type
Finset.card_eq_two.mp
if a finite set has cardinality 2, it consists of two distinct elements
Finset.mem_univ
every element of a finite type belongs to the universal finset of that type
Finset.mem_insert
an element belongs to the insertion of b into a finite set s if and only if it equals b or belongs to s
Finset.mem_singleton
an element belongs to the singleton set {a} if and only if it equals a

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

/-- Any graph on at most 2 vertices has a dominating pair of vertices. -/theorem dominating_pair_of_card_le_two {V : Type*} [Fintype V] (G : SimpleGraph V)    [Nonempty V] (h : Fintype.card V ≤ 2) :    ∃ u v : V, ∀ w : V, w = u ∨ w = v ∨ G.Adj u w ∨ G.Adj v w := by  classical  by_cases h1 : Fintype.card V ≤ 1  · obtain ⟨u⟩ := ‹Nonempty V›    refine ⟨u, u, fun w => ?_⟩    left    exact Fintype.card_le_one_iff.mp h1 w u  · have h2 : Fintype.card V = 2 := by omega    have hc : (Finset.univ : Finset V).card = 2 := by      rw [Finset.card_univ]; exact h2    obtain ⟨x, y, hxy, hset⟩ := Finset.card_eq_two.mp hc    refine ⟨x, y, fun w => ?_⟩    have hw : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w    rw [hset] at hw    simp only [Finset.mem_insert, Finset.mem_singleton] at hw    rcases hw with rfl | rfl    · left; rfl    · right; left; rfl
See it in the graphDiscuss this resultChallenge it