AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_every_proper_cycle_unsafe

theoremverified

Every proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.

Statement

theorem digraph_safe17_every_proper_cycle_unsafe
    (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C)
    (hproper : C ≠ Finset.univ) :
    ∃ v ∉ C, 3 ≤ (C.filter fun w => digraph_safe17_graph.Adj v w).card
Source
Safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
Used by 1

The proof, explained

The proof proceeds by contradiction: assuming a proper directed cycle C has no outside vertex with at least 3 outneighbors on C, every outside vertex has at most 2 outneighbors on C (making C safe). The cycle definition ensures |C| ≥ 2, and properness ensures the complement of C is nonempty. The argument then splits on the size of C: sizes |C| ≥ 5 are ruled out by a general lemma against long safe sets, while small cycles of sizes 2, 3, and 4 are each ruled out by specialized lemmas showing no such cycle can exist or be safe.

  1. Adjacency between any two vertices in the graph is decidable. automation

    Given two vertices u and v, unfolding the definition of digraph_safe17_graph reveals that adjacency is testing whether (v - u) belongs to the explicit set {1, 2, 3, 5, 6, 7, 13}, which Lean resolves automatically by typeclass inference.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Assuming the theorem fails, every outside vertex has at most two outneighbors in C.

    We argue by contradiction, assuming there is no vertex outside C with 3 or more outneighbors in C. Consequently, for any v ∉ C, the number of edges from v into C must be at most 2, since having 3 or more would contradict our assumption.

    lines 10–15

      classical
      by_contra h
      have hsafe : ∀ v ∉ C, (C.filter fun w => digraph_safe17_graph.Adj v w).card ≤ 2 := by
        intro v hv
        by_contra hn
        exact h ⟨v,hv,by omega⟩
  3. There exists at least one vertex outside C.

    Since C is assumed to be a proper subset of vertices (C ≠ Finset.univ), its complement cannot be empty: if every vertex were in C, C would equal Finset.univ by extensionality, contradicting the properness hypothesis.

    lines 16–22

    uses Finset.mem_univ, iff_true

      have hne : ∃ v, v ∉ C := by
        by_contra hn
        apply hproper
        ext v
        simp only [Finset.mem_univ, iff_true]
        by_contra hv
        exact hn ⟨v,hv⟩
  4. The cycle C has cardinality at least 2.

    By definition of a directed cycle (digraph_directed_cycle_on), C is the vertex set of a duplicate-free list of length at least 2. Since the list has no duplicates, |C| equals the list's length, which is at least 2.

    lines 23–27

    uses List.toFinset_card_of_nodup

      have hmin : 2 ≤ C.card := by
        obtain ⟨l,hn,hlen,hset,_,_⟩ := hcycle
        have hc := List.toFinset_card_of_nodup hn
        rw [hset] at hc
        omega
  5. The cycle C cannot have cardinality 5 or greater.

    We split on whether |C| ≥ 5. When |C| ≥ 5, the lemma digraph_safe17_no_long_safe_set directly asserts that no proper safe set in this graph can have 5 or more vertices, producing a contradiction.

    lines 28–29

    uses digraph_safe17_no_long_safe_set

      by_cases hlarge : 5 ≤ C.card
      · exact digraph_safe17_no_long_safe_set C hne hlarge hsafe
  6. The remaining cases |C| ∈ {2, 3, 4} are impossible, completing the contradiction.

    Since 2 ≤ |C| and |C| < 5, integer arithmetic leaves only |C| = 2, |C| = 3, or |C| = 4. Each case is eliminated by an existing lemma: digraph_safe17_two_cycle_impossible shows the graph has no 2-cycles, digraph_safe17_triangle_cycle_unsafe shows no 3-cycle is safe, and digraph_safe17_four_cycle_unsafe shows no 4-cycle is safe.

    lines 30–34

    uses digraph_safe17_two_cycle_impossible, digraph_safe17_triangle_cycle_unsafe, digraph_safe17_four_cycle_unsafe

      · have hcases : C.card = 2 ∨ C.card = 3 ∨ C.card = 4 := by omega
        rcases hcases with h2 | h3 | h4
        · exact digraph_safe17_two_cycle_impossible C hcycle h2
        · exact digraph_safe17_triangle_cycle_unsafe C hcycle h3 hsafe
        · exact digraph_safe17_four_cycle_unsafe C hcycle h4 hsafe
digraph_safe17_four_cycle_unsafe
In this 17-vertex graph, no directed 4-cycle is safe (every 4-cycle has an outside vertex with at least 3 outneighbors on it).
digraph_safe17_no_long_safe_set
In this 17-vertex graph, there is no safe proper subset of vertices of cardinality 5 or greater.
digraph_safe17_triangle_cycle_unsafe
In this 17-vertex graph, no directed 3-cycle is safe (every triangle has an outside vertex with at least 3 outneighbors on it).
digraph_safe17_two_cycle_impossible
In this 17-vertex graph, there are no directed 2-cycles.
Finset.mem_univ
Every element of a finite type belongs to the universal set `Finset.univ`.
iff_true
A proposition P is equivalent to (P ↔ True).
List.toFinset_card_of_nodup
The cardinality of the set of elements of a list without duplicates is equal to the length of the list.

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_full : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_every_proper_cycle_unsafe    (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C)    (hproper : C ≠ Finset.univ) :    ∃ v ∉ C, 3 ≤ (C.filter fun w => digraph_safe17_graph.Adj v w).card := by  classical  by_contra h  have hsafe : ∀ v ∉ C, (C.filter fun w => digraph_safe17_graph.Adj v w).card ≤ 2 := by    intro v hv    by_contra hn    exact h ⟨v,hv,by omega⟩  have hne : ∃ v, v ∉ C := by    by_contra hn    apply hproper    ext v    simp only [Finset.mem_univ, iff_true]    by_contra hv    exact hn ⟨v,hv⟩  have hmin : 2 ≤ C.card := by    obtain ⟨l,hn,hlen,hset,_,_⟩ := hcycle    have hc := List.toFinset_card_of_nodup hn    rw [hset] at hc    omega  by_cases hlarge : 5 ≤ C.card  · exact digraph_safe17_no_long_safe_set C hne hlarge hsafe  · have hcases : C.card = 2 ∨ C.card = 3 ∨ C.card = 4 := by omega    rcases hcases with h2 | h3 | h4    · exact digraph_safe17_two_cycle_impossible C hcycle h2    · exact digraph_safe17_triangle_cycle_unsafe C hcycle h3 hsafe    · exact digraph_safe17_four_cycle_unsafe C hcycle h4 hsafe
See it in the graphDiscuss this resultChallenge it