AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_triangle_unsafe

theoremverified

Every directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.

Statement

theorem digraph_safe17_triangle_unsafe (u a b : Fin 17)
    (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)
    (hbu : digraph_safe17_graph.Adj b u) :
    ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧
      digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧
      digraph_safe17_graph.Adj x b
Source
Finite safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

To show that every directed triangle (u, a, b) has an outside common predecessor, the proof translates the triangle by -u so that u becomes 0. It then invokes the rooted case `digraph_safe17_rooted_triangle_unsafe`, which provides an outside common predecessor x for the translated triangle (0, a - u, b - u). Finally, shifting x back by +u yields the required vertex x + u pointing to u, a, and b.

  1. Adjacency in the graph is decidable. automation

    Given any two vertices u and v, unfolding the definition of the graph shows adjacency is membership in a finite set, which is decidable by typeclass synthesis.

    lines 1–4

    private instance in504_safe17_decAdj_5 : DecidableRel digraph_safe17_graph.Adj := by
      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Translating both vertices by -u preserves adjacency: Adj (x - u) (y - u) ↔ Adj x y.

    Using the translation invariance of the graph (`digraph_safe17_shift`) by the offset -u and rewriting subtraction as addition of the negative, we establish that shifting by -u preserves adjacency.

    lines 12–14

    uses sub_eq_add_neg, digraph_safe17_shift

      have hn (x y : Fin 17) : digraph_safe17_graph.Adj (x-u) (y-u) ↔
          digraph_safe17_graph.Adj x y := by
        simpa only [sub_eq_add_neg] using digraph_safe17_shift x y (-u)
  3. The translated vertices 0, a - u, and b - u form a directed triangle.

    Applying the shift equivalence to the original edges u → a, a → b, and b → u shows that 0 → a - u, a - u → b - u, and b - u → 0, forming a directed triangle containing 0.

    lines 15–17

      have h1 : digraph_safe17_graph.Adj 0 (a-u) := by simpa using (hn u a).2 hua
      have h2 := (hn a b).2 hab
      have h3 : digraph_safe17_graph.Adj (b-u) 0 := by simpa using (hn b u).2 hbu
  4. There exists a common predecessor x for the shifted triangle (0, a - u, b - u).

    By `digraph_safe17_rooted_triangle_unsafe`, any directed triangle containing 0 has an outside vertex x pointing to all three vertices 0, a - u, and b - u.

    line 18

    uses digraph_safe17_rooted_triangle_unsafe

      obtain ⟨x,hx0,hxa,hxb,hu,ha,hb⟩ := digraph_safe17_rooted_triangle_unsafe (a-u) (b-u) h1 h2 h3
  5. If x is distinct from v - u, then x + u is distinct from v.

    Assuming x + u = v, subtracting u from both sides via `congrArg` would give x = v - u, contradicting the assumption that x ≠ v - u.

    lines 19–23

    uses congrArg

      have hne (v : Fin 17) (hv : x ≠ v-u) : x+u ≠ v := by
        intro he
        apply hv
        have ht := congrArg (fun z : Fin 17 => z-u) he
        simpa using ht
  6. If x points to v - u, then x + u points to v.

    Shifting the edge from x to v - u by +u via `digraph_safe17_shift` gives an edge from x + u to (v - u) + u = v.

    lines 24–26

    uses digraph_safe17_shift

      have back (v : Fin 17) (hv : digraph_safe17_graph.Adj x (v-u)) :
          digraph_safe17_graph.Adj (x+u) v := by
        simpa using (digraph_safe17_shift x (v-u) u).2 hv
  7. The vertex x + u is the desired outside vertex pointing to u, a, and b.

    We instantiate the existential witness with x + u. Since x is distinct from 0, a - u, and b - u, x + u is distinct from u, a, and b. Moreover, shifting the edges x → a - u and x → b - u gives edges x + u → a and x + u → b, and shifting x → 0 gives an edge x + u → u.

    lines 27–28

    uses digraph_safe17_shift

      refine ⟨x+u,hne u (by simpa using hx0),hne a hxa,hne b hxb,?_,back a ha,back b hb⟩
      simpa using (digraph_safe17_shift x 0 u).2 hu
sub_eq_add_neg
Subtracting an element equals adding its additive inverse.
digraph_safe17_shift
Shifting both vertices by any offset t preserves directed adjacency in this circulant graph.
digraph_safe17_rooted_triangle_unsafe
Every directed triangle with one vertex at 0 has a common outside predecessor.
congrArg
Functions preserve equality: if x = y, then f(x) = f(y).

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

private instance in504_safe17_decAdj_5 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_triangle_unsafe (u a b : Fin 17)    (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)    (hbu : digraph_safe17_graph.Adj b u) :    ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧      digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧      digraph_safe17_graph.Adj x b := by  have hn (x y : Fin 17) : digraph_safe17_graph.Adj (x-u) (y-u) ↔      digraph_safe17_graph.Adj x y := by    simpa only [sub_eq_add_neg] using digraph_safe17_shift x y (-u)  have h1 : digraph_safe17_graph.Adj 0 (a-u) := by simpa using (hn u a).2 hua  have h2 := (hn a b).2 hab  have h3 : digraph_safe17_graph.Adj (b-u) 0 := by simpa using (hn b u).2 hbu  obtain ⟨x,hx0,hxa,hxb,hu,ha,hb⟩ := digraph_safe17_rooted_triangle_unsafe (a-u) (b-u) h1 h2 h3  have hne (v : Fin 17) (hv : x ≠ v-u) : x+u ≠ v := by    intro he    apply hv    have ht := congrArg (fun z : Fin 17 => z-u) he    simpa using ht  have back (v : Fin 17) (hv : digraph_safe17_graph.Adj x (v-u)) :      digraph_safe17_graph.Adj (x+u) v := by    simpa using (digraph_safe17_shift x (v-u) u).2 hv  refine ⟨x+u,hne u (by simpa using hx0),hne a hxa,hne b hxb,?_,back a ha,back b hb⟩  simpa using (digraph_safe17_shift x 0 u).2 hu
See it in the graphDiscuss this resultChallenge it