digraph_safe17_every_proper_cycle_unsafe
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
- 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_triangle_unsafeEvery directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.
- digraph_safe17_four_unsafeEvery directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.
- digraph_oriented_safe_set_indegree_boundIn a finite loopless oriented digraph of minimum indegree r, a set to which each outside vertex sends at most two arcs satisfies r times…
- digraph_safe17_no_long_safe_setEvery proper set of at least five vertices in the displayed graph has an outside vertex with at least three outneighbors in the set.
- digraph_safe17_two_cycle_impossibleThe displayed oriented graph has no directed cycle on two vertices.
- digraph_safe17_triangle_cycle_unsafeNo directed triangle in the displayed graph is safe for deletion with a two-neighbor budget.
- digraph_safe17_four_cycle_unsafeNo directed four-cycle in the displayed graph is safe for deletion with a two-neighbor budget.
- Used by 1
- digraph_safe_cycle_universal_criterion_falseIt is false that every loopless oriented seven-diregular graph on seventeen vertices with a complete common-predecessor graph contains a…
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.
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.
intro u v unfold digraph_safe17_graph infer_instance
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.
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⟩
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.
uses
Finset.mem_univ,iff_truehave 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⟩
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.
uses
List.toFinset_card_of_noduphave hmin : 2 ≤ C.card := by obtain ⟨l,hn,hlen,hset,_,_⟩ := hcycle have hc := List.toFinset_card_of_nodup hn rw [hset] at hc omega
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.
uses
digraph_safe17_no_long_safe_setby_cases hlarge : 5 ≤ C.card · exact digraph_safe17_no_long_safe_set C hne hlarge hsafe
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.
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.
- The auxiliary instance at lines 1–4 establishes that edge adjacency in digraph_safe17_graph is decidable, which Lean requires to form and count vertex neighborhoods such as the filter expression in the theorem statement.
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_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