not_not_isContained_book_graph_of_commonNeighbors_le
The statement not_isContained_book_graph_of_commonNeighbors_le is false: The statement is FALSE for k = 0.
Under Lean's Nat subtraction, 0 - 1 = 0.
When k = 0, the hypothesis h requires that every pair of adjacent vertices u, v in G has at most 0 - 1 = 0 common neighbors, which holds for any triangle-free graph, such as the complete graph G = K_2 on two vertices.
However, book_graph 0 is the book graph with 0 pages, whose vertex set is Fin 2 ⊕ Fin 0 ≃ Fin 2, consisting solely of the single edge between Sum.inl 0 and Sum.inl 1.
Thus book_graph 0 is isomorphic to K_2, which is contained in G = K_2.
Therefore, (book_graph 0).IsContained G holds, contradicting ¬ (book_graph 0).IsContained G.
Statement
theorem not_not_isContained_book_graph_of_commonNeighbors_le : ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ u v : V, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ k - 1), ¬ (book_graph k).IsContained G)
- Related work
- refutes `not_isContained_book_graph_of_commonNeighbors_le`
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- book_graphThe book graph B_n is the graph consisting of n triangles sharing a common edge (spine), formalized on vertices Fin 2 ⊕ Fin n.
The proof, explained
The proof refutes the universal claim by providing an explicit counterexample at k = 0, choosing G to be the complete graph K_2 on two vertices. Because truncated subtraction on ℕ gives 0 - 1 = 0, the hypothesis requires adjacent vertices to share at most 0 common neighbors, which holds because K_2 has only two vertices in total. Furthermore, the 0-page book graph consists of a single edge and thus embeds directly into K_2. This contradicts the conclusion that G cannot contain the 0-page book graph.
Assume for contradiction the universal statement.
We introduce the assumed hypothesis H, which asserts that for any finite graph G and any k, if adjacent vertices share at most k - 1 common neighbors, then G cannot contain the k-page book graph.
intro HThe 0-page book graph embeds into the complete graph on two vertices.
We construct an embedding of `book_graph 0` into the complete graph ⊤ on ULift (Fin 2). Because Fin 0 has no elements, every vertex of `book_graph 0` (defined on Fin 2 ⊕ Fin 0) originates from Fin 2 and is mapped to the corresponding lifted vertex. Two vertices in `book_graph 0` are adjacent only when they are distinct vertices in Fin 2; since adjacency in the complete graph is distinctness (by `top_adj`), adjacency is preserved. Injectivity holds because equality of images in ULift implies equality in Fin 2 (by `ULift.ext_iff.mp`), with all other cases eliminated vacuously.
uses
top_adj,ULift.ext_iff.mpopen SimpleGraph in have hc : (book_graph 0).IsContained (⊤ : SimpleGraph (ULift (Fin 2))) := by refine ⟨⟨⟨fun x => match x with | Sum.inl i => ⟨i⟩ | Sum.inr i => i.elim0, ?_⟩, ?_⟩⟩ · rintro (x | x) (y | y) h · rw [top_adj] intro heq exact h (ULift.ext_iff.mp heq) · exact y.elim0 · exact x.elim0 · exact x.elim0 · rintro (x | x) (y | y) h · congr exact ULift.ext_iff.mp h · exact y.elim0 · exact x.elim0 · exact x.elim0
Every pair of adjacent vertices in the complete graph on two vertices has at most 0 - 1 common neighbors.
For any adjacent vertices u and v in the two-vertex complete graph, a common neighbor w must be distinct from both u and v by `SimpleGraph.top_adj`, expanding the definition of common neighbors via `SimpleGraph.commonNeighbors`, `Set.mem_inter_iff`, and `SimpleGraph.mem_neighborSet`. Exhausting all possible values for u, v, and w in Fin 2 shows that no such vertex w can exist, so the common neighbor set is empty. By `Fintype.card_eq_zero`, its cardinality is 0, which satisfies 0 ≤ 0 - 1.
uses
SimpleGraph.commonNeighbors,Set.mem_inter_iff,SimpleGraph.mem_neighborSet,SimpleGraph.top_adj,Fintype.card_eq_zerohave hh : ∀ u v : ULift (Fin 2), (⊤ : SimpleGraph (ULift (Fin 2))).Adj u v → Fintype.card ((⊤ : SimpleGraph (ULift (Fin 2))).commonNeighbors u v) ≤ 0 - 1 := by intro ⟨u⟩ ⟨v⟩ huv have : IsEmpty ((⊤ : SimpleGraph (ULift (Fin 2))).commonNeighbors ⟨u⟩ ⟨v⟩) := by refine ⟨fun ⟨⟨w⟩, hw⟩ => ?_⟩ simp only [SimpleGraph.commonNeighbors, Set.mem_inter_iff, SimpleGraph.mem_neighborSet, SimpleGraph.top_adj] at hw fin_cases u <;> fin_cases v <;> fin_cases w <;> tauto rw [Fintype.card_eq_zero]
A contradiction is reached, refuting the assumed statement.
We instantiate the universal hypothesis H with V = ULift (Fin 2), G = ⊤, and k = 0. Since the common neighbor bound and the containment of `book_graph 0` both hold, H yields False, completing the proof by contradiction.
exact @H (ULift (Fin 2)) _ _ ⊤ _ 0 hh hc
top_adj- In the complete graph ⊤, two vertices are adjacent if and only if they are distinct.
ULift.ext_iff.mp- If two lifted elements in ULift α are equal, their underlying values in α are equal.
SimpleGraph.commonNeighbors- The set of common neighbors of two vertices in a simple graph is defined as the intersection of their neighbor sets.
Set.mem_inter_iff- An element belongs to the intersection of two sets if and only if it belongs to both sets.
SimpleGraph.mem_neighborSet- A vertex w is in the neighbor set of v if and only if v and w are adjacent.
SimpleGraph.top_adj- In the complete graph ⊤, two vertices are adjacent if and only if they are distinct.
Fintype.card_eq_zero- A finite type has cardinality zero if and only if it is empty.
- Under Lean's truncated subtraction on natural numbers, 0 - 1 = 0, so the hypothesis for k = 0 requires that adjacent vertices have at most 0 common neighbors, which holds for K_2.
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.
theorem not_not_isContained_book_graph_of_commonNeighbors_le : ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ u v : V, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ k - 1), ¬ (book_graph k).IsContained G) := by intro H open SimpleGraph in have hc : (book_graph 0).IsContained (⊤ : SimpleGraph (ULift (Fin 2))) := by refine ⟨⟨⟨fun x => match x with | Sum.inl i => ⟨i⟩ | Sum.inr i => i.elim0, ?_⟩, ?_⟩⟩ · rintro (x | x) (y | y) h · rw [top_adj] intro heq exact h (ULift.ext_iff.mp heq) · exact y.elim0 · exact x.elim0 · exact x.elim0 · rintro (x | x) (y | y) h · congr exact ULift.ext_iff.mp h · exact y.elim0 · exact x.elim0 · exact x.elim0 have hh : ∀ u v : ULift (Fin 2), (⊤ : SimpleGraph (ULift (Fin 2))).Adj u v → Fintype.card ((⊤ : SimpleGraph (ULift (Fin 2))).commonNeighbors u v) ≤ 0 - 1 := by intro ⟨u⟩ ⟨v⟩ huv have : IsEmpty ((⊤ : SimpleGraph (ULift (Fin 2))).commonNeighbors ⟨u⟩ ⟨v⟩) := by refine ⟨fun ⟨⟨w⟩, hw⟩ => ?_⟩ simp only [SimpleGraph.commonNeighbors, Set.mem_inter_iff, SimpleGraph.mem_neighborSet, SimpleGraph.top_adj] at hw fin_cases u <;> fin_cases v <;> fin_cases w <;> tauto rw [Fintype.card_eq_zero] exact @H (ULift (Fin 2)) _ _ ⊤ _ 0 hh hc