AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_four_unsafe

theoremverified

Every directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.

Statement

theorem digraph_safe17_four_unsafe (u a b c : Fin 17)
    (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)
    (hbc : digraph_safe17_graph.Adj b c) (hcu : digraph_safe17_graph.Adj c u) :
    ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧
      ((digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b) ∨
       (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x c) ∨
       (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c) ∨
       (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c))
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

The proof reduces the existence of a dominating outside vertex for an arbitrary directed 4-cycle $u \to a \to b \to c \to u$ to the rooted case where one vertex is 0, by translating all vertices by $-u$. Because edge adjacency on $\mathbb{Z}/17\mathbb{Z}$ is translation-invariant, the shifted cycle forms a valid 4-cycle rooted at 0, allowing us to invoke digraph_safe17_rooted_four_unsafe to obtain a witness $x$. Finally, translating $x$ back to $x+u$ preserves both its distinctness from the cycle vertices and all directed edges, producing the desired outside vertex for the original cycle.

  1. Adjacency in the graph is decidable.

    By unfolding the definition of adjacency in digraph_safe17_graph, whether an edge exists between $u$ and $v$ reduces to checking whether $(v-u).val$ belongs to a specific finite set of natural numbers, which Lean infers automatically as a decidable relation.

    lines 1–4

    private instance in504_safe17_decAdj_6 : DecidableRel digraph_safe17_graph.Adj := by
      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Adjacency is invariant under subtracting $u$: $x - u \to y - u$ if and only if $x \to y$.

    Shifting both vertices by $-u$ preserves adjacency by digraph_safe17_shift, and rewriting subtraction as addition of the negation via sub_eq_add_neg simplifies $(x + -u)$ and $(y + -u)$ to $x - u$ and $y - u$.

    lines 14–16

    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 shifted vertices $0, a-u, b-u, c-u$ form a directed 4-cycle rooted at 0.

    Applying shift-invariance (hn) to each of the four edges $u \to a$, $a \to b$, $b \to c$, and $c \to u$, and noting that $u - u = 0$, yields edges $0 \to a-u$, $a-u \to b-u$, $b-u \to c-u$, and $c-u \to 0$.

    lines 17–20

      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 := (hn b c).2 hbc
      have h4 : digraph_safe17_graph.Adj (c-u) 0 := by simpa using (hn c u).2 hcu
  4. There exists a vertex $x \in \mathbb{Z}/17\mathbb{Z}$ outside the shifted 4-cycle that points to at least three of its vertices.

    We apply digraph_safe17_rooted_four_unsafe to the shifted 4-cycle $0 \to a-u \to b-u \to c-u \to 0$, obtaining an outside vertex $x$ (distinct from $0, a-u, b-u, c-u$) that has edges to at least three of those four vertices.

    line 21

    uses digraph_safe17_rooted_four_unsafe

      obtain ⟨x,hx0,hxa,hxb,hxc,htrip⟩ := digraph_safe17_rooted_four_unsafe (a-u) (b-u) (c-u) h1 h2 h3 h4
  5. Translating $x$ back by adding $u$ preserves distinctness from the cycle vertices: $x + u \neq u, a, b, c$.

    We establish the helper lemma hne: if $x + u = v$, subtracting $u$ from both sides using congrArg would give $x = v - u$, contradicting $x \neq v - u$. Applying this with $v = u$ and using $x \neq 0$ proves $x + u \neq u$.

    lines 22–27

    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
      have hxu : x+u ≠ u := hne u (by simpa using hx0)
  6. Edges from $x$ in the shifted cycle translate back to edges from $x+u$: $x \to v-u$ implies $x+u \to v$, and $x \to 0$ implies $x+u \to u$.

    Applying digraph_safe17_shift by adding $u$ maps the edge $x \to v-u$ to $(x+u) \to (v-u+u) = v$, and maps $x \to 0$ to $(x+u) \to u$.

    lines 28–32

    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
      have back0 (hv : digraph_safe17_graph.Adj x 0) : digraph_safe17_graph.Adj (x+u) u := by
        simpa using (digraph_safe17_shift x 0 u).2 hv
  7. The translated vertex $x+u$ is an outside vertex pointing to at least three vertices of the original cycle $u, a, b, c$.

    We provide $x+u$ as the witness. Its distinctness from $u, a, b, c$ follows from the previous step. We then perform a case analysis on the four possible 3-subsets dominated by $x$ in the shifted cycle; in each case, the back-translation lemmas yield the three corresponding edges from $x+u$ to the vertices in the original cycle.

    lines 33–38

    uses Or.inl, Or.inr

      refine ⟨x+u,hxu,hne a hxa,hne b hxb,hne c hxc,?_⟩
      rcases htrip with h | h | h | h
      · exact Or.inl ⟨back0 h.1,back a h.2.1,back b h.2.2⟩
      · exact Or.inr (Or.inl ⟨back0 h.1,back a h.2.1,back c h.2.2⟩)
      · exact Or.inr (Or.inr (Or.inl ⟨back0 h.1,back b h.2.1,back c h.2.2⟩))
      · exact Or.inr (Or.inr (Or.inr ⟨back a h.1,back b h.2.1,back c h.2.2⟩))
sub_eq_add_neg
In a subtraction-negation monoid, subtracting $b$ is equal to adding the negative of $b$: $a - b = a + (-b)$.
digraph_safe17_shift
In the graph, adjacency is invariant under translation by any element $t$: there is an edge $(a+t) \to (b+t)$ if and only if there is an edge $a \to b$.
digraph_safe17_rooted_four_unsafe
Every directed 4-cycle rooted at 0 ($0 \to a \to b \to c \to 0$) in the graph has an outside vertex pointing to at least three of its vertices.
congrArg
Applying a function to equal inputs yields equal outputs: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Or.inl
Constructs a proof of a disjunction $A \lor B$ from a proof of the left disjunct $A$.
Or.inr
Constructs a proof of a disjunction $A \lor B$ from a proof of the right disjunct $B$.

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_6 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_four_unsafe (u a b c : Fin 17)    (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)    (hbc : digraph_safe17_graph.Adj b c) (hcu : digraph_safe17_graph.Adj c u) :    ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧      ((digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b) ∨       (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x c) ∨       (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c) ∨       (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c)) := 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 := (hn b c).2 hbc  have h4 : digraph_safe17_graph.Adj (c-u) 0 := by simpa using (hn c u).2 hcu  obtain ⟨x,hx0,hxa,hxb,hxc,htrip⟩ := digraph_safe17_rooted_four_unsafe (a-u) (b-u) (c-u) h1 h2 h3 h4  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 hxu : x+u ≠ u := hne u (by simpa using hx0)  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  have back0 (hv : digraph_safe17_graph.Adj x 0) : digraph_safe17_graph.Adj (x+u) u := by    simpa using (digraph_safe17_shift x 0 u).2 hv  refine ⟨x+u,hxu,hne a hxa,hne b hxb,hne c hxc,?_⟩  rcases htrip with h | h | h | h  · exact Or.inl ⟨back0 h.1,back a h.2.1,back b h.2.2⟩  · exact Or.inr (Or.inl ⟨back0 h.1,back a h.2.1,back c h.2.2⟩)  · exact Or.inr (Or.inr (Or.inl ⟨back0 h.1,back b h.2.1,back c h.2.2⟩))  · exact Or.inr (Or.inr (Or.inr ⟨back a h.1,back b h.2.1,back c h.2.2⟩))
See it in the graphDiscuss this resultChallenge it