AFTD Auto-Formalizing Theoretical Domains

digraph_safe_cycle_universal_criterion_false

theoremverified

It is false that every loopless oriented seven-diregular graph on seventeen vertices with a complete common-predecessor graph contains a proper directed cycle whose deletion costs every remaining vertex at most two outneighbors.

Statement

theorem digraph_safe_cycle_universal_criterion_false :
    ¬ (∀ (D : Digraph (Fin 17)) [DecidableRel D.Adj],
      (∀ u, ¬ D.Adj u u) →
      (∀ u v, D.Adj u v → ¬ D.Adj v u) →
      (∀ u, (Finset.univ.filter fun v => D.Adj u v).card = 7) →
      (∀ v, (Finset.univ.filter fun u => D.Adj u v).card = 7) →
      (∀ u v, u ≠ v → ∃ p, D.Adj p u ∧ D.Adj p v) →
      ∃ C : Finset (Fin 17), C ≠ Finset.univ ∧ digraph_directed_cycle_on D C ∧
        ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2)
Source
Safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
  • digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
  • digraph_safe17_structureThe displayed graph is oriented and seven-diregular, and every two distinct vertices have a common predecessor.
  • digraph_safe17_every_proper_cycle_unsafeEvery proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.

The proof, explained

The universal criterion is disproved by counterexample using an explicit 17-vertex circulant tournament-like digraph, digraph_safe17_graph. This graph satisfies all the regularity, orientation, and predecessor conditions, yet by an exhaustive structural property, every one of its proper directed cycles has an external vertex with at least three directed edges into it, directly contradicting the requirement of at most two.

  1. The adjacency relation on the digraph digraph_safe17_graph is decidable.

    Given any two vertices u and v, adjacency is defined by the condition that (v - u).val belongs to the explicit set {1, 2, 3, 5, 6, 7, 13}. Lean's typeclass inference synthesizes the decidability of this finite-set membership condition.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Assuming the universal criterion, the concrete 17-vertex digraph digraph_safe17_graph must contain a proper directed cycle where every external vertex has at most two edges into the cycle.

    Assume for contradiction that the universal statement holds. The lemma digraph_safe17_structure shows that digraph_safe17_graph is a valid instance: it is loopless, oriented, 7-diregular, and has common predecessors for all pairs of distinct vertices. Instantiating the assumed universal statement with this graph yields a proper directed cycle C such that every vertex v ∉ C has at most two outneighbors in C.

    lines 18–20

    uses digraph_safe17_structure

      intro h
      obtain ⟨hloop,hori,hout,hin,hcommon⟩ := digraph_safe17_structure
      obtain ⟨C,hproper,hcycle,hsafe⟩ := h digraph_safe17_graph hloop hori hout hin hcommon
  3. A contradiction arises because every proper directed cycle in digraph_safe17_graph admits an external vertex with at least three edges into it.

    By digraph_safe17_every_proper_cycle_unsafe, any proper directed cycle C in digraph_safe17_graph has some vertex v ∉ C with at least 3 edges directed into C. Specializing the cycle's safety property to v gives that v has at most 2 edges into C. Linear integer arithmetic (via omega) detects the contradiction between 3 ≤ card and card ≤ 2, completing the refutation.

    lines 21–23

    uses digraph_safe17_every_proper_cycle_unsafe

      obtain ⟨v,hv,hthree⟩ := digraph_safe17_every_proper_cycle_unsafe C hcycle hproper
      have htwo := hsafe v hv
      omega
digraph_safe17_structure
The digraph digraph_safe17_graph is loopless, oriented, 7-in-regular, 7-out-regular, and every pair of distinct vertices shares a common predecessor.
digraph_safe17_every_proper_cycle_unsafe
For every proper directed cycle C in digraph_safe17_graph, there exists a vertex outside C with at least three directed edges into C.

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_6 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe_cycle_universal_criterion_false :    ¬ (∀ (D : Digraph (Fin 17)) [DecidableRel D.Adj],      (∀ u, ¬ D.Adj u u) →      (∀ u v, D.Adj u v → ¬ D.Adj v u) →      (∀ u, (Finset.univ.filter fun v => D.Adj u v).card = 7) →      (∀ v, (Finset.univ.filter fun u => D.Adj u v).card = 7) →      (∀ u v, u ≠ v → ∃ p, D.Adj p u ∧ D.Adj p v) →      ∃ C : Finset (Fin 17), C ≠ Finset.univ ∧ digraph_directed_cycle_on D C ∧        ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) := by  intro h  obtain ⟨hloop,hori,hout,hin,hcommon⟩ := digraph_safe17_structure  obtain ⟨C,hproper,hcycle,hsafe⟩ := h digraph_safe17_graph hloop hori hout hin hcommon  obtain ⟨v,hv,hthree⟩ := digraph_safe17_every_proper_cycle_unsafe C hcycle hproper  have htwo := hsafe v hv  omega
See it in the graphDiscuss this resultChallenge it