dominating_pair_of_card_le_two
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.
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.
classical by_cases h1 : Fintype.card V ≤ 1If |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.
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
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}.
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
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.
uses
Finset.mem_univ,Finset.mem_insert,Finset.mem_singletonrefine ⟨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
- The theorem's definition of a dominating pair allows vertices to be dominated either by equality or by adjacency; here, because the graph has at most two vertices, the pair covers all vertices by equality alone, without using any edges.
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.
/-- 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