digraph_semicomplete_multipartite_nonadj_trans
In a semicomplete multipartite digraph D, non-adjacency in both directions is transitive among pairwise distinct vertices.
Statement
theorem digraph_semicomplete_multipartite_nonadj_trans {V : Type*} (D : Digraph V) (hmulti : digraph_is_semicomplete_multipartite D) {u v w : V} (huv : ¬ D.Adj u v ∧ ¬ D.Adj v u) (hvw : ¬ D.Adj v w ∧ ¬ D.Adj w v) (h : u ≠ w) : ¬ D.Adj u w ∧ ¬ D.Adj w u
- Source
- step towards digraph_four_strong_semicomplete_multipartite_nonadjacent_pairs_linked
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_is_semicomplete_multipartiteA digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e.,…
The proof, explained
A digraph D is semicomplete multipartite when its underlying simple graph D.toSimpleGraphInclusive is complete multipartite, which formally means that non-adjacency is a transitive relation. Given that there are no directed edges in either direction between u and v, and likewise between v and w, both pairs are non-adjacent in the underlying simple graph. Transitivity then implies u and w are non-adjacent in the underlying simple graph, from which it follows (since u ≠ w) that no directed edge exists between u and w in either direction.
Non-adjacency in the underlying simple graph of D is a transitive relation.
By definition, a digraph D is semicomplete multipartite if it has no self-loops and its underlying undirected graph D.toSimpleGraphInclusive is complete multipartite. Unpacking hmulti yields htrans, which states that non-adjacency in the simple graph is transitive.
obtain ⟨-, htrans⟩ := hmultiThe vertices u and v are non-adjacent in D.toSimpleGraphInclusive.
Adjacency in D.toSimpleGraphInclusive between two vertices requires that they are distinct and connected by a directed edge in at least one direction. Since huv states that there is no directed edge between u and v in either direction, the simplifier concludes they are non-adjacent in D.toSimpleGraphInclusive.
uses
Digraph.toSimpleGraphInclusive,SimpleGraph.fromRel_adjhave h1 : ¬ D.toSimpleGraphInclusive.Adj u v := by simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, huv]
The vertices v and w are non-adjacent in D.toSimpleGraphInclusive.
Analogously, since hvw states that there is no directed edge in either direction between v and w, the simplifier shows that v and w are non-adjacent in D.toSimpleGraphInclusive.
uses
Digraph.toSimpleGraphInclusive,SimpleGraph.fromRel_adjhave h2 : ¬ D.toSimpleGraphInclusive.Adj v w := by simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, hvw]
The vertices u and w are non-adjacent in D.toSimpleGraphInclusive.
Since non-adjacency in D.toSimpleGraphInclusive is transitive (htrans), applying IsTrans.trans to the non-adjacency of u and v (h1) and that of v and w (h2) establishes that u and w are non-adjacent in the simple graph.
uses
IsTrans.transhave h3 : ¬ D.toSimpleGraphInclusive.Adj u w := @IsTrans.trans V _ htrans u v w h1 h2There is no directed edge between u and w in either direction in D.
Unfolding the definition of adjacency in D.toSimpleGraphInclusive at h3 reveals that ¬(u ≠ w ∧ (D.Adj u w ∨ D.Adj w u)). Because u ≠ w by assumption, propositional reasoning (tauto) entails ¬D.Adj u w ∧ ¬D.Adj w u.
uses
Digraph.toSimpleGraphInclusive,SimpleGraph.fromRel_adjrw [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj] at h3 tauto
Digraph.toSimpleGraphInclusive- The simple graph constructed from a digraph with vertices V, having an undirected edge between any two distinct vertices that are connected by a directed edge in either direction.
IsTrans.trans- Transitivity of a binary relation: if r a b and r b c, then r a c.
SimpleGraph.fromRel_adj- Two vertices v and w are adjacent in the simple graph generated by a relation r if and only if v ≠ w and either r v w or r w v holds.
- In Mathlib, a simple graph is defined to be complete multipartite (`SimpleGraph.IsCompleteMultipartite`) specifically as the transitivity of its non-adjacency relation (`IsTrans V (fun x y => ¬G.Adj x y)`), rather than via an explicit partition into independent sets.
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.
/-- In a semicomplete multipartite digraph D, non-adjacency in both directions is transitive among pairwise distinct vertices. -/theorem digraph_semicomplete_multipartite_nonadj_trans {V : Type*} (D : Digraph V) (hmulti : digraph_is_semicomplete_multipartite D) {u v w : V} (huv : ¬ D.Adj u v ∧ ¬ D.Adj v u) (hvw : ¬ D.Adj v w ∧ ¬ D.Adj w v) (h : u ≠ w) : ¬ D.Adj u w ∧ ¬ D.Adj w u := by obtain ⟨-, htrans⟩ := hmulti have h1 : ¬ D.toSimpleGraphInclusive.Adj u v := by simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, huv] have h2 : ¬ D.toSimpleGraphInclusive.Adj v w := by simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, hvw] have h3 : ¬ D.toSimpleGraphInclusive.Adj u w := @IsTrans.trans V _ htrans u v w h1 h2 rw [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj] at h3 tauto