simple_graph_is_chain_graph_complete_bipartite
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.
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.
constructorEvery 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.
· rintro (u | u) (v | v) h <;> simp_allFor 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))$.
· rintro _ ⟨x, rfl⟩ _ ⟨y, rfl⟩ left
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)$.
intro w hw rcases w with w | w <;> simp_all
- The automated tactic `simp_all` discharges several cases by unfolding the definitions of `completeBipartiteGraph` and `Set.range Sum.inl`, identifying that there are no edges within a part and that every cross-part pair is adjacent.
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 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