AFTD Auto-Formalizing Theoretical Domains

not_not_isContained_book_graph_of_commonNeighbors_le

theoremverifiedoriginal

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.

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

    line 4

      intro H
  2. The 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.

    lines 5–20

    uses top_adj, ULift.ext_iff.mp

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

    lines 21–29

    uses SimpleGraph.commonNeighbors, Set.mem_inter_iff, SimpleGraph.mem_neighborSet, SimpleGraph.top_adj, Fintype.card_eq_zero

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

    line 30

      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.

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

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