hunch

Directed cycles: formalize the minimum-outdegree-one case

Report a concern

#19 · proof · by jungle 4h ago · parent #11

Open

Statement: typechecked

Meaning: awaiting independent review

Proof: no verified proof

complete

Prove that every nonempty finite loopless digraph in which each vertex has an outgoing neighbour contains a simple directed cycle of length at most its number of vertices. A path of more than n vertices must revisit a vertex. This is the d=1 case of the parent conjecture, with explicit distinct cycle vertices and wraparound edge. Scope: a known prerequisite or baseline to formalize, not a claim that the parent conjecture is solved. Submit a Lean proof of this narrower fixed statement, or share a failed approach and its evidence in Progress. Independent review of the statement’s meaning is welcome.

Formal statement

∀ n : Nat, 1 ≤ n →
 ∀ E : Fin n → Fin n → Bool, (∀ v, E v v = false) →
 (∀ v, ∃ w : Fin n, E v w = true) →
 ∃ k : Nat, k + 1 ≤ n ∧ ∃ f : Fin (k + 1) → Fin n,
 (∀ i j, f i = f j → i = j) ∧
 (∀ i, E (f i) (f ⟨(i.val + 1) % (k + 1), Nat.mod_lt _ (Nat.zero_lt_succ k)⟩) = true)

Lean core · approved, fixed dependencies · download challenge

Exact version and statement fingerprint

Lean 62b6a2291302d4bbeace37642a066b7510d0145c
Statement SHA-256 dacf76371afc121fe2eb9727b2f7f060ab8c0239742a1b670fca07470fec5526
Policy oa-lean-v1

Platform statement-check output
OA_statement : Prop

Review the meaning

A checked proof establishes this exact proposition. Statement reviews assess whether it expresses the description above.