AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_triangle_cycle_unsafe

theoremverified

No directed triangle in the displayed graph is safe for deletion with a two-neighbor budget.

Statement

theorem digraph_safe17_triangle_cycle_unsafe
    (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C)
    (hcard : C.card = 3)
    (hsafe : ∀ x ∉ C, (C.filter fun w => digraph_safe17_graph.Adj x w).card ≤ 2) : False
Source
Safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

Any directed cycle of size 3 in the graph must consist of three distinct vertices forming a directed triangle. By a previously established graph property, every directed triangle has an external vertex with directed edges to all three of its vertices. This external vertex therefore has 3 in-neighbors in the cycle, contradicting the assumption that every external vertex has at most 2 in-neighbors in the cycle.

  1. The adjacency relation of the digraph is decidable.

    For any two vertices u and v, unfolding the definition of the graph reduces adjacency to checking whether the integer value of (v - u) belongs to the set {1, 2, 3, 5, 6, 7, 13}, which Lean's typeclass inference resolves as decidable set membership.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. The cycle C is represented by a duplicate-free list of vertices connected cyclically.

    Unpacking the definition of a directed cycle on C yields a list l without duplicates whose set of elements is C, whose consecutive elements are adjacent, and whose last element is adjacent to its head.

    lines 13–14

      classical
      obtain ⟨l,hn,hlen0,hset,hchain,hclose⟩ := hcycle
  3. The list l has length 3.

    Since l has no duplicates, List.toFinset_card_of_nodup equates its length to the cardinality of its underlying finset, which is C; since |C| = 3, integer arithmetic closes the goal.

    lines 15–18

    uses List.toFinset_card_of_nodup

      have hlen : l.length = 3 := by
        have h := List.toFinset_card_of_nodup hn
        rw [hset,hcard] at h
        omega
  4. The list l consists of three vertices u, a, b.

    By case analysis on the list l, any length other than 3 contradicts the known length, leaving only the shape l = [u, a, b].

    lines 19–32

      have hshape : ∃ u a b, l = [u,a,b] := by
        cases l with
        | nil => simp at hlen
        | cons u l =>
          cases l with
          | nil => simp at hlen
          | cons a l =>
            cases l with
            | nil => simp at hlen
            | cons b l =>
              cases l with
              | nil => exact ⟨u,a,b,rfl⟩
              | cons c l => simp at hlen
      obtain ⟨u,a,b,rfl⟩ := hshape
  5. The vertices u, a, b are pairwise distinct, span C, and form a directed triangle.

    Because l = [u, a, b], its vertex set is {u, a, b} = C. The chain condition decomposes via List.isChain_cons_cons into edges u → a and a → b. The cycle closure condition gives b → u using List.head?_cons and Option.some.injEq. Duplicate-freeness of l yields pairwise distinctness of u, a, b with and_assoc.

    lines 33–43

    uses List.isChain_cons_cons, List.head?_cons, Option.some.injEq, and_assoc

      have hcset : ({u,a,b} : Finset (Fin 17)) = C := by simpa using hset
      have hchain' : digraph_safe17_graph.Adj u a ∧ digraph_safe17_graph.Adj a b := by
        simpa [List.isChain_cons_cons] using hchain
      have hbu : digraph_safe17_graph.Adj b u := by
        obtain ⟨x,y,hx,hy,hxy⟩ := hclose
        simp only [List.head?_cons, Option.some.injEq] at hx
        simp at hy
        subst x
        subst y
        exact hxy
      have hdistinct : u ≠ a ∧ u ≠ b ∧ a ≠ b := by simpa [and_assoc] using hn
  6. There exists an external vertex v outside C with directed edges to u, a, and b.

    Applying the lemma digraph_safe17_triangle_unsafe to the directed triangle u → a → b → u provides a vertex v distinct from u, a, and b (hence not in C) with edges v → u, v → a, and v → b.

    lines 44–46

    uses digraph_safe17_triangle_unsafe

      obtain ⟨v,hvu,hva,hvb,hv0,hv1,hv2⟩ :=
        digraph_safe17_triangle_unsafe u a b hchain'.1 hchain'.2 hbu
      have hv : v ∉ C := by rw [← hcset]; simp [hvu,hva,hvb]
  7. The existence of three edges from an external vertex contradicts the safety condition, proving False.

    The lemma digraph_safe17_three_neighbors_not_safe shows that having an external vertex v ∉ C with directed edges to three distinct vertices u, a, b ∈ C directly contradicts the hypothesis that every external vertex has at most 2 neighbors in C.

    lines 47–54

    uses digraph_safe17_three_neighbors_not_safe

      apply digraph_safe17_three_neighbors_not_safe C v u a b hv hdistinct.1 hdistinct.2.1 hdistinct.2.2
      · rw [← hcset]; simp
      · rw [← hcset]; simp
      · rw [← hcset]; simp
      · exact hv0
      · exact hv1
      · exact hv2
      · exact hsafe
List.toFinset_card_of_nodup
The cardinality of the finset of elements of a duplicate-free list equals the length of the list.
List.isChain_cons_cons
A list with at least two elements is a chain with respect to a relation R if and only if R holds between the first two elements and the tail is a chain.
List.head?_cons
The optional head of a cons list `a :: l` is `some a`.
Option.some.injEq
`some x = some y` is equivalent to `x = y`.
and_assoc
Conjunction is associative: `(P ∧ Q) ∧ R` is equivalent to `P ∧ Q ∧ R`.
digraph_safe17_triangle_unsafe
For every directed triangle in the graph, there exists a fourth vertex with directed edges to all three triangle vertices.
digraph_safe17_three_neighbors_not_safe
If an external vertex has directed edges to three distinct vertices of a subset C, then C violates the 2-neighbor budget safety condition.

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_final_decAdj_2 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe17_triangle_cycle_unsafe    (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C)    (hcard : C.card = 3)    (hsafe : ∀ x ∉ C, (C.filter fun w => digraph_safe17_graph.Adj x w).card ≤ 2) : False := by  classical  obtain ⟨l,hn,hlen0,hset,hchain,hclose⟩ := hcycle  have hlen : l.length = 3 := by    have h := List.toFinset_card_of_nodup hn    rw [hset,hcard] at h    omega  have hshape : ∃ u a b, l = [u,a,b] := by    cases l with    | nil => simp at hlen    | cons u l =>      cases l with      | nil => simp at hlen      | cons a l =>        cases l with        | nil => simp at hlen        | cons b l =>          cases l with          | nil => exact ⟨u,a,b,rfl⟩          | cons c l => simp at hlen  obtain ⟨u,a,b,rfl⟩ := hshape  have hcset : ({u,a,b} : Finset (Fin 17)) = C := by simpa using hset  have hchain' : digraph_safe17_graph.Adj u a ∧ digraph_safe17_graph.Adj a b := by    simpa [List.isChain_cons_cons] using hchain  have hbu : digraph_safe17_graph.Adj b u := by    obtain ⟨x,y,hx,hy,hxy⟩ := hclose    simp only [List.head?_cons, Option.some.injEq] at hx    simp at hy    subst x    subst y    exact hxy  have hdistinct : u ≠ a ∧ u ≠ b ∧ a ≠ b := by simpa [and_assoc] using hn  obtain ⟨v,hvu,hva,hvb,hv0,hv1,hv2⟩ :=    digraph_safe17_triangle_unsafe u a b hchain'.1 hchain'.2 hbu  have hv : v ∉ C := by rw [← hcset]; simp [hvu,hva,hvb]  apply digraph_safe17_three_neighbors_not_safe C v u a b hv hdistinct.1 hdistinct.2.1 hdistinct.2.2  · rw [← hcset]; simp  · rw [← hcset]; simp  · rw [← hcset]; simp  · exact hv0  · exact hv1  · exact hv2  · exact hsafe
See it in the graphDiscuss this resultChallenge it