not_digraph_ckk_subdivision_three_exceptional
The statement digraph_ckk_subdivision_three_exceptional is false: The statement omits any nonemptiness hypothesis on the vertex type, so it is false for the empty digraph. Take V = PEmpty (the empty type, available in every universe, with Fintype instance) and D := ⟨fun _ _ => False⟩. Then:
* hloop : ∀ v, ¬ D.Adj v v holds vacuously;
* hmin : ∀ v, 1 ≤ digraph_out_degree D v holds vacuously;
* digraph_exceptional_verts D is Finset.filter _ Finset.univ over the empty type, i.e. ∅, so (...).card = 0 ≤ 3, giving hexc;
* digraph_has_digirth_ge D g holds vacuously: for any c : List PEmpty, c must be [] (length 0), contradicting the required 2 ≤ c.length;
* but digraph_has_ckk_subdivision D k is ∃ u : V, ..., which is uninhabited, hence false for every k (in particular for k = 2, where hk : 2 ≤ 2).
Thus every hypothesis is satisfiable while the conclusion fails, so ¬ (∀ {V} [Fintype V] (D : Digraph V) [DecidableRel D.Adj], ...) is provable; the refutation body is machine-checked at an arbitrary universe level. (This is the only obstruction I found: for k = 2 the small nonempty cases with digirth ≥ 4 and ≤ 3 exceptional vertices — e.g. small circulants — do exhibit the C(k,k) subdivision, consistent with the intended, nonempty statement.)
Statement
open Classical in theorem not_digraph_ckk_subdivision_three_exceptional : ¬ (∀ {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (hloop : ∀ v : V, ¬ D.Adj v v) (k : ℕ) (hk : 2 ≤ k) (hmin : ∀ v : V, 1 ≤ digraph_out_degree D v) (hexc : (digraph_exceptional_verts D).card ≤ 3) (hgirth : digraph_has_digirth_ge D (3 * (k - 1) + 1)), digraph_has_ckk_subdivision D k)
- Related work
- refutes `digraph_ckk_subdivision_three_exceptional`
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- digraph_exceptional_vertsFor a finite directed graph D on a finite vertex type V with decidable adjacency, the set of exceptional vertices O(D) is the finite set…
- digraph_out_degreeThe out-degree d⁺(v) of a vertex v in a finite directed graph D is the number of out-neighbors of v, that is, the cardinality of the set…
- digraph_has_digirth_geA digraph D has digirth at least g if every directed cycle of length at least 2 in D (represented by a list c of distinct vertices with 2…
- digraph_has_ckk_subdivisionA digraph D contains a subdivision of C(k,k) if there exist two distinct vertices u, v and two internally vertex-disjoint directed paths…
- digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
Lean source view module on GitHub
open Classical in theorem not_digraph_ckk_subdivision_three_exceptional : ¬ (∀ {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (hloop : ∀ v : V, ¬ D.Adj v v) (k : ℕ) (hk : 2 ≤ k) (hmin : ∀ v : V, 1 ≤ digraph_out_degree D v) (hexc : (digraph_exceptional_verts D).card ≤ 3) (hgirth : digraph_has_digirth_ge D (3 * (k - 1) + 1)), digraph_has_ckk_subdivision D k) := by intro h have hexc : (digraph_exceptional_verts (V := PEmpty) ⟨fun _ _ => False⟩).card ≤ 3 := by have : digraph_exceptional_verts (V := PEmpty) ⟨fun _ _ => False⟩ = ∅ := by ext x exact x.elim rw [this] simp have hgirth : digraph_has_digirth_ge (V := PEmpty) ⟨fun _ _ => False⟩ (3 * (2 - 1) + 1) := by intro c hc rcases c with _ | ⟨x, xs⟩ · have hlen := hc.2.1 change 2 ≤ 0 at hlen cases hlen · exact x.elim have hckk := h (V := PEmpty) ⟨fun _ _ => False⟩ (by intro v; exact v.elim) 2 (by norm_num) (by intro v; exact v.elim) hexc hgirth rcases hckk with ⟨u, -⟩ exact u.elim