simple_graph_indepNum_le_one_imp_eq_top
If G is not the complete graph, there exist two distinct non-adjacent vertices, forming an independent set of size 2, so indepNum G >= 2. By contrapositive, indepNum G <= 1 implies G = ⊤.
Statement
theorem simple_graph_indepNum_le_one_imp_eq_top {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hα : G.indepNum ≤ 1) : G = ⊤
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We prove the contrapositive by graph extensionality: to show G = ⊤, it suffices to show that any two distinct vertices are adjacent in G. If there were two distinct vertices u and v with no edge between them, the pair {u, v} would form an independent set of size 2. This would force G.indepNum ≥ 2, contradicting the hypothesis that G.indepNum ≤ 1.
To show G = ⊤, it suffices to show that any two distinct vertices are adjacent in G.
By extensionality on simple graphs, two graphs are identical if they have the same adjacency relation. In the complete graph ⊤, adjacency is equivalent to inequality of vertices (`SimpleGraph.top_adj`). The forward direction holds because adjacent vertices in a simple graph are always distinct (`G.ne_of_adj`), leaving the reverse direction: any pair of distinct vertices must be adjacent.
uses
SimpleGraph.top_adj,G.ne_of_adjext u v rw [SimpleGraph.top_adj] constructor · intro h exact G.ne_of_adj h
Suppose, for contradiction, that there are distinct vertices u and v that are not adjacent in G.
To prove the remaining implication, we assume u ≠ v and assume for contradiction that u and v are not adjacent in G.
· intro hne by_contra h_not_adj
The two-element set {u, v}, regarded as a finite set, is an independent set in G.
By definition (`SimpleGraph.IsIndepSet`), an independent set is one whose distinct vertices are never adjacent. For a pair {u, v}, `Set.pairwise_pair` reduces this to checking that u is not adjacent to v and v is not adjacent to u, which follows from the non-adjacency of u and v and the symmetry of adjacency (`G.adj_symm`). Applying `Finset.coe_pair` establishes that the finite set {u, v} is an independent set.
uses
SimpleGraph.IsIndepSet,Set.pairwise_pair,G.adj_symm,Finset.coe_pairhave h_indep : G.IsIndepSet ({u, v} : Set V) := by rw [SimpleGraph.IsIndepSet, Set.pairwise_pair] intro _ exact ⟨h_not_adj, fun hvu => h_not_adj (G.adj_symm hvu)⟩ have h_indep' : G.IsIndepSet ↑({u, v} : Finset V) := by rwa [Finset.coe_pair]
The independence number of G is at least 2.
Any independent finite set has size at most the independence number of G (`card_le_indepNum`). Since u ≠ v, the pair {u, v} has cardinality 2 (`Finset.card_pair_eq_two_iff.mpr`), which yields 2 ≤ G.indepNum.
uses
Finset.card_pair_eq_two_iff.mprhave h_card_le := h_indep'.card_le_indepNum have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair_eq_two_iff.mpr hne rw [h_card] at h_card_le
The inequality 2 ≤ G.indepNum contradicts the hypothesis G.indepNum ≤ 1.
Having both G.indepNum ≤ 1 and 2 ≤ G.indepNum is impossible; linear arithmetic over ℕ (`omega`) derives False and completes the proof.
omega
SimpleGraph.top_adj- In the complete graph ⊤, two vertices are adjacent if and only if they are distinct.
G.ne_of_adj- In any simple graph G, adjacent vertices are distinct.
SimpleGraph.IsIndepSet- A set of vertices is independent if no two distinct vertices in the set are adjacent.
Set.pairwise_pair- A pair {a, b} is pairwise related by r if and only if a ≠ b implies both r a b and r b a.
G.adj_symm- Adjacency in a simple graph G is a symmetric relation.
Finset.coe_pair- The coercion of the finite set pair {a, b} to a Set equals {a, b}.
Finset.card_pair_eq_two_iff.mpr- If two elements are distinct, the finite set containing them has cardinality 2.
- The coercion step between `{u, v} : Set V` and `{u, v} : Finset V` via `Finset.coe_pair` is a type-theoretic distinction: in Lean, graph independence is defined on arbitrary sets (`Set V`), whereas the independence number `indepNum` is defined in terms of finite sets (`Finset V`).
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.
/-- Every finite simple graph with independence number at most 1 is the complete graph. -/theorem simple_graph_indepNum_le_one_imp_eq_top {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hα : G.indepNum ≤ 1) : G = ⊤ := by ext u v rw [SimpleGraph.top_adj] constructor · intro h exact G.ne_of_adj h · intro hne by_contra h_not_adj have h_indep : G.IsIndepSet ({u, v} : Set V) := by rw [SimpleGraph.IsIndepSet, Set.pairwise_pair] intro _ exact ⟨h_not_adj, fun hvu => h_not_adj (G.adj_symm hvu)⟩ have h_indep' : G.IsIndepSet ↑({u, v} : Finset V) := by rwa [Finset.coe_pair] have h_card_le := h_indep'.card_le_indepNum have h_card : ({u, v} : Finset V).card = 2 := Finset.card_pair_eq_two_iff.mpr hne rw [h_card] at h_card_le omega