digraph_common_cycle_core_outside_injection
In a strongly connected finite vertex set, suppose all directed cycles contain a core K and every vertex in a subset S of K has at least two outneighbors inside the set. Then there are at least |S| vertices outside K.
Statement
theorem digraph_common_cycle_core_outside_injection (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T K S : Finset α) (hKT : K ⊆ T) (hSK : S ⊆ K) (hloop : ∀ v, ¬ D.Adj v v) (hstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → K ⊆ C) (hdeg : ∀ v ∈ S, 2 ≤ (T.filter fun w => D.Adj v w).card) : S.card ≤ (T \ K).card
- Source
- Common-cycle core counting for the oriented twenty-cut profile.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_common_cycle_core_neighbor_uniqueInside a strongly connected finite set, if every directed cycle contains a fixed core, every vertex has at most one outgoing neighbor and…
- 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…
- 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…
- Used by 2
- digraph_17_shared_target_forces_two_cyclesThe normalized oriented seventeen-vertex shared-target configuration with three designated parents contains two disjoint cycles, assuming…
- digraph_16_shared_target_forces_two_cyclesThe normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.
The proof, explained
The proof constructs an injective function from S into the complement T \ K, from which |S| ≤ |T \ K| follows immediately. For each s ∈ S, since s has at least two outneighbors in T but can have at most one in K by cycle-core uniqueness, it must have at least one outneighbor outside K. Choosing one such outneighbor for each s defines a map f : S → T \ K, which is injective because cycle-core uniqueness also guarantees that each vertex in T \ K has at most one inneighbor in K.
Every vertex in T has at most one outneighbor in K and at most one inneighbor in K.
We apply the cycle core uniqueness lemma (digraph_common_cycle_core_neighbor_unique) to T and the cycle core K. Under the hypotheses that T is strongly connected without self-loops and that every directed cycle in T contains K, this establishes that for every vertex x ∈ T, both |N⁺(x) ∩ K| ≤ 1 and |N⁻(x) ∩ K| ≤ 1.
uses
digraph_common_cycle_core_neighbor_uniqueclassical have hu := digraph_common_cycle_core_neighbor_unique α D T K hKT hloop hstrong hcoreEvery vertex s ∈ S has at least one outneighbor in T \ K.
Fix s ∈ S. Since S ⊆ K ⊆ T, s lies in both K and T. Suppose, for contradiction, that s has no outneighbors in T \ K. Then every outneighbor of s in T must also belong to K, meaning the outneighborhood of s in T is a subset of its outneighborhood in K. By Finset.card_le_card, the outdegree of s in T is bounded by its outdegree into K. However, by assumption s has at least 2 outneighbors in T, while the uniqueness lemma limits its outneighbors in K to at most 1. Linear arithmetic over ℕ (omega) detects the resulting contradiction 2 ≤ 1.
uses
Finset.mem_filter.mp,Finset.mem_sdiff.mpr,Finset.mem_filter.mpr,Finset.card_le_cardhave hex : ∀ s ∈ S, ∃ x ∈ T \ K, D.Adj s x := by intro s hs have hsK : s ∈ K := hSK hs have hsT : s ∈ T := hKT hsK by_contra hn have hsub : (T.filter fun w => D.Adj s w) ⊆ (K.filter fun w => D.Adj s w) := by intro w hw have hwT : w ∈ T := (Finset.mem_filter.mp hw).1 have hadj : D.Adj s w := (Finset.mem_filter.mp hw).2 have hwK : w ∈ K := by by_contra hwK exact hn ⟨w,Finset.mem_sdiff.mpr ⟨hwT,hwK⟩,hadj⟩ exact Finset.mem_filter.mpr ⟨hwK,hadj⟩ have hc := Finset.card_le_card hsub have hd := hdeg s hs have hbound := (hu s hsT).1 omega
There is a well-defined map f : S → T \ K sending each vertex in S to an outneighbor outside K.
Using the witness provided by the existence property proved above, we define f on the subtype of elements in S by choosing, for each s ∈ S, an outneighbor f(s) ∈ T \ K such that there is a directed edge from s to f(s).
let f : {s : α // s ∈ S} → {x : α // x ∈ T \ K} := fun s => ⟨(hex s.val s.property).choose, (hex s.val s.property).choose_spec.1⟩
The mapping f is injective.
Suppose f(a) = f(b) = x for two vertices a, b ∈ S. Then x ∈ T \ K ⊆ T, and both a and b are directed inneighbors of x. Because S ⊆ K, both a and b lie in K, so both are elements of the inneighborhood of x inside K. By our uniqueness lemma, x has at most one inneighbor in K, so any two elements of this set must be equal (Finset.card_le_one.mp). Thus a = b, establishing that f is injective.
uses
Subtype.ext,congrArg,Finset.mem_sdiff.mp,Finset.card_le_one.mp,Finset.mem_filter.mprhave hf : Function.Injective f := by intro a b heq apply Subtype.ext have ax := (hex a.val a.property).choose_spec.2 have bx := (hex b.val b.property).choose_spec.2 have hx : (f a).val = (f b).val := congrArg Subtype.val heq have hxT : (f a).val ∈ T := (Finset.mem_sdiff.mp (f a).property).1 have haK : a.val ∈ K := hSK a.property have hbK : b.val ∈ K := hSK b.property have hcard := (hu (f a).val hxT).2 apply (Finset.card_le_one.mp hcard) a.val (Finset.mem_filter.mpr ⟨haK, ax⟩) b.val (Finset.mem_filter.mpr ⟨hbK, ?_⟩) change D.Adj b.val (f b).val at bx simpa [hx] using bx
The cardinality of S is at most the cardinality of T \ K.
By Fintype.card_le_of_injective, the existence of an injection from S to T \ K implies that the cardinality of the domain cannot exceed that of the codomain. Simplifying this inequality converts the subtype cardinalities to finset cardinalities, concluding |S| ≤ |T \ K|.
uses
Fintype.card_le_of_injectivehave hh := Fintype.card_le_of_injective f hf simpa using hh
digraph_common_cycle_core_neighbor_unique- In a strongly connected finite vertex set without loops where all directed cycles contain K, every vertex has at most one outneighbor in K and at most one inneighbor in K.
Finset.mem_filter.mp- An element of a filtered finset belongs to the original finset and satisfies the filtering predicate.
Finset.mem_filter.mpr- An element that belongs to a finset and satisfies a predicate belongs to the filtered finset.
Finset.mem_sdiff.mpr- An element in a set s that is not in a set t belongs to the difference s \ t.
Finset.mem_sdiff.mp- An element belonging to s \ t belongs to s and does not belong to t.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the cardinality of the other.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congrArg- Applying a function to equal inputs yields equal outputs.
Finset.card_le_one.mp- In a finset with at most one element, any two elements are equal.
Fintype.card_le_of_injective- An injective map between finite types implies the domain's cardinality is at most the codomain's cardinality.
- The injection is constructed formally between the subtype {s // s ∈ S} and the subtype {x // x ∈ T \ K}, with the final step converting the subtype cardinality inequality into the finset cardinality inequality.
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.
set_option maxHeartbeats 3000000set_option maxRecDepth 4096theorem digraph_common_cycle_core_outside_injection (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T K S : Finset α) (hKT : K ⊆ T) (hSK : S ⊆ K) (hloop : ∀ v, ¬ D.Adj v v) (hstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → K ⊆ C) (hdeg : ∀ v ∈ S, 2 ≤ (T.filter fun w => D.Adj v w).card) : S.card ≤ (T \ K).card := by classical have hu := digraph_common_cycle_core_neighbor_unique α D T K hKT hloop hstrong hcore have hex : ∀ s ∈ S, ∃ x ∈ T \ K, D.Adj s x := by intro s hs have hsK : s ∈ K := hSK hs have hsT : s ∈ T := hKT hsK by_contra hn have hsub : (T.filter fun w => D.Adj s w) ⊆ (K.filter fun w => D.Adj s w) := by intro w hw have hwT : w ∈ T := (Finset.mem_filter.mp hw).1 have hadj : D.Adj s w := (Finset.mem_filter.mp hw).2 have hwK : w ∈ K := by by_contra hwK exact hn ⟨w,Finset.mem_sdiff.mpr ⟨hwT,hwK⟩,hadj⟩ exact Finset.mem_filter.mpr ⟨hwK,hadj⟩ have hc := Finset.card_le_card hsub have hd := hdeg s hs have hbound := (hu s hsT).1 omega let f : {s : α // s ∈ S} → {x : α // x ∈ T \ K} := fun s => ⟨(hex s.val s.property).choose, (hex s.val s.property).choose_spec.1⟩ have hf : Function.Injective f := by intro a b heq apply Subtype.ext have ax := (hex a.val a.property).choose_spec.2 have bx := (hex b.val b.property).choose_spec.2 have hx : (f a).val = (f b).val := congrArg Subtype.val heq have hxT : (f a).val ∈ T := (Finset.mem_sdiff.mp (f a).property).1 have haK : a.val ∈ K := hSK a.property have hbK : b.val ∈ K := hSK b.property have hcard := (hu (f a).val hxT).2 apply (Finset.card_le_one.mp hcard) a.val (Finset.mem_filter.mpr ⟨haK, ax⟩) b.val (Finset.mem_filter.mpr ⟨hbK, ?_⟩) change D.Adj b.val (f b).val at bx simpa [hx] using bx have hh := Fintype.card_le_of_injective f hf simpa using hh