digraph_safe_cycle_universal_criterion_false
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.
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.
intro u v unfold digraph_safe17_graph infer_instance
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.
uses
digraph_safe17_structureintro h obtain ⟨hloop,hori,hout,hin,hcommon⟩ := digraph_safe17_structure obtain ⟨C,hproper,hcycle,hsafe⟩ := h digraph_safe17_graph hloop hori hout hin hcommon
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.
uses
digraph_safe17_every_proper_cycle_unsafeobtain ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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