AFTD Auto-Formalizing Theoretical Domains

digraph_semicomplete_multipartite_nonadj_trans

theoremverified

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

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.

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

    line 6

      obtain ⟨-, htrans⟩ := hmulti
  2. The 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.

    lines 7–8

    uses Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj

      have h1 : ¬ D.toSimpleGraphInclusive.Adj u v := by
        simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, huv]
  3. 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.

    lines 9–10

    uses Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj

      have h2 : ¬ D.toSimpleGraphInclusive.Adj v w := by
        simp [Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj, hvw]
  4. 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.

    line 11

    uses IsTrans.trans

      have h3 : ¬ D.toSimpleGraphInclusive.Adj u w := @IsTrans.trans V _ htrans u v w h1 h2
  5. There 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.

    lines 12–13

    uses Digraph.toSimpleGraphInclusive, SimpleGraph.fromRel_adj

      rw [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.

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

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