AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_chain_graph_complete_bipartite

theoremverified

The complete bipartite graph K_{a,b} is a chain graph (all vertices on one side have the same neighbourhood).

Statement

theorem simple_graph_is_chain_graph_complete_bipartite (a b : ℕ) :
    simple_graph_is_chain_graph (completeBipartiteGraph (Fin a) (Fin b)) (Set.range Sum.inl)
Source
Sanity lemma for the definition of chain graphs, arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination).
Verified
14 Oct 2026
Axioms
Quot.soundpropext
Built on 1
  • simple_graph_is_chain_graphG is a chain graph with bipartition (A, V \ A): every edge joins A to its complement, and the neighbourhoods of the vertices of A are…

The proof, explained

To show that the complete bipartite graph $K_{a,b}$ is a chain graph with respect to the left part $A = \operatorname{range}(\operatorname{inl})$, the proof verifies the two defining conditions: bipartiteness and nested neighborhoods. First, a case analysis on the sides of two adjacent vertices confirms that edges only connect vertices on opposite sides. Second, because every vertex on the left has the exact same neighborhood (the entire right side), any two left vertices have identical neighborhoods, which trivially implies that one neighborhood is a subset of the other.

  1. The goal reduces to proving bipartiteness and the nested neighborhood property for vertices in $A = \operatorname{range}(\operatorname{inl})$.

    By definition, a graph is a chain graph with respect to a vertex subset $A$ if (1) every edge connects a vertex in $A$ to a vertex outside $A$, and (2) for any two vertices in $A$, their neighborhoods are totally ordered by inclusion. Splitting the conjunction produces these two subgoals.

    line 3

      constructor
  2. Every edge in the complete bipartite graph connects a vertex in $A$ to a vertex outside $A$.

    We consider the four cases for the parts containing adjacent vertices $u$ and $v$. If both lie in the left part $\operatorname{Fin}(a)$ or both in the right part $\operatorname{Fin}(b)$, they cannot be adjacent by definition of the complete bipartite graph, which contradicts the edge hypothesis. If one lies on the left and the other on the right, exactly one belongs to $A = \operatorname{range}(\operatorname{inl})$, so $u \in A \iff v \notin A$ holds in both cross cases.

    line 4

      · rintro (u | u) (v | v) h <;> simp_all
  3. For any two vertices $\operatorname{inl}(x), \operatorname{inl}(y) \in A$, it suffices to show that the neighborhood of $\operatorname{inl}(x)$ is a subset of the neighborhood of $\operatorname{inl}(y)$.

    Any vertices in $A = \operatorname{range}(\operatorname{inl})$ can be written as $\operatorname{inl}(x)$ and $\operatorname{inl}(y)$ for some $x, y \in \operatorname{Fin}(a)$. To establish that one neighborhood is contained in the other, we choose the forward inclusion $N(\operatorname{inl}(x)) \subseteq N(\operatorname{inl}(y))$.

    lines 5–6

      · rintro _ ⟨x, rfl⟩ _ ⟨y, rfl⟩
        left
  4. Every neighbor of $\operatorname{inl}(x)$ is also a neighbor of $\operatorname{inl}(y)$.

    Let $w$ be a neighbor of $\operatorname{inl}(x)$. We case-split on whether $w$ belongs to the left or right part. If $w = \operatorname{inl}(w')$, both $w$ and $\operatorname{inl}(x)$ lie in the left part, contradicting their adjacency. Thus $w = \operatorname{inr}(w')$ lies in the right part, and by the definition of the complete bipartite graph, it is adjacent to every vertex in the left part, in particular to $\operatorname{inl}(y)$.

    lines 7–8

        intro w hw
        rcases w with w | w <;> simp_all

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 simple_graph_is_chain_graph_complete_bipartite (a b : ℕ) :    simple_graph_is_chain_graph (completeBipartiteGraph (Fin a) (Fin b)) (Set.range Sum.inl) := by  constructor  · rintro (u | u) (v | v) h <;> simp_all  · rintro _ ⟨x, rfl⟩ _ ⟨y, rfl⟩    left    intro w hw    rcases w with w | w <;> simp_all
See it in the graphDiscuss this resultChallenge it