digraph_finite_sink_strong_subgraph
Every nonempty finite vertex set contains a nonempty strongly connected subset with no outgoing arc to the rest of that set.
Statement
theorem digraph_finite_sink_strong_subgraph (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (H : Finset α) (hne : H.Nonempty) : ∃ T : Finset α, T ⊆ H ∧ T.Nonempty ∧ (∀ x ∈ T, ∀ y ∈ H, D.Adj x y → y ∈ T) ∧ (∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T)
- Source
- Finite directed sink-component fact used in the oriented twenty-cut profile.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_is_directed_path_singletonFor every digraph D and vertex v, the singleton list [v] is a directed path from v to v.
- 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
We consider the family of all nonempty subsets of H with no outgoing edges to H \ S. Since H is finite and belongs to this family, we can choose an element T of minimum cardinality. To show that T is strongly connected, we fix u ∈ T and consider the set R_u of vertices in T reachable from u by a directed path in T. Because T has no outgoing edges to H \ T, extending or truncating a path along an edge stays in T, which implies R_u also has no outgoing edges to H \ R_u and thus belongs to the family. By minimality of |T|, we have T = R_u, so every vertex in T is reachable from u.
When y ∈ p, the prefix of p ending at y is a directed path from u to y with all vertices in T.
We split into cases based on whether y already occurs on p. If y ∈ p, we decompose p as l₁ ++ [y] ++ l₂. The prefix l₁ ++ [y] inherits the chain and nodup properties from p, has head u (by checking whether l₁ is empty or not), has last element y, and its vertices all lie in T because they are vertices of p.
uses
List.append_of_mem,List.nil_append,List.head?_cons,List.cons_appendby_cases hy : y ∈ p · obtain ⟨l₁, l₂, rfl⟩ := List.append_of_mem hy have hpref : l₁ ++ [y] <+: l₁ ++ y :: l₂ := ⟨l₂, by simp⟩ refine ⟨l₁ ++ [y], ⟨?_, ?_, ?_, ?_⟩, ?_⟩ · exact hp.1.prefix hpref · exact hp.2.1.sublist hpref.sublist · cases l₁ with | nil => simp only [List.nil_append, List.head?_cons] at hp ⊢ exact hp.2.2.1 | cons w ws => simp only [List.cons_append, List.head?_cons] at hp ⊢ exact hp.2.2.1 · simp · intro z hz exact hpT z (hpref.subset hz)
When y ∉ p, appending y to p yields a directed path from u to y with all vertices in T.
If y ∉ p, we unpack p into its chain, nodup, head, and last element properties. Since p has head u, p is nonempty. We append [y] to p: the chain property holds because the last element of p is x and D.Adj x y; nodup holds because p has no duplicates, [y] has none, and y ∉ p; the head is still u; the last element is y; and all vertices are in T since the vertices of p and y are in T.
uses
List.IsChain.append,List.IsChain.singleton,Option.mem_some_iff,List.head?_cons,List.nodup_append,List.nodup_singleton,List.mem_singleton,List.head?_append_of_ne_nil,List.getLast?_append_cons,List.mem_append· rcases hp with ⟨hchain, hnodup, hhead, hlast⟩ have hp_ne : p ≠ [] := by rintro rfl simp at hhead refine ⟨p ++ [y], ⟨?_, ?_, ?_, ?_⟩, ?_⟩ · apply List.IsChain.append hchain (List.IsChain.singleton y) intro a ha b hb simp only [hlast, Option.mem_some_iff] at ha simp only [List.head?_cons, Option.mem_some_iff] at hb subst ha hb exact hadj · rw [List.nodup_append] refine ⟨hnodup, List.nodup_singleton y, ?_⟩ intro a ha b hb simp only [List.mem_singleton] at hb subst hb rintro rfl exact hy ha · rw [List.head?_append_of_ne_nil _ hp_ne] exact hhead · rw [List.getLast?_append_cons] simp · intro z hz simp only [List.mem_append, List.mem_singleton] at hz rcases hz with hz | rfl · exact hpT z hz · exact hyT
There exists a nonempty subset T ⊆ H closed under outgoing edges to H of minimum cardinality.
We define closed_subsets to be the family of all nonempty subsets S ⊆ H such that no edge in D goes from S to H \ S. The set H itself belongs to this family, so the family is nonempty. Because the vertex set is finite, there exists an element T in closed_subsets minimizing cardinality. We unpack the properties that T ⊆ H, T is nonempty, and T is closed under outgoing edges to H.
uses
Finset.mem_filter,Finset.mem_powerset_self,Finset.exists_min_image,Finset.mem_powersetclassical let closed_subsets : Finset (Finset α) := H.powerset.filter (fun S => S.Nonempty ∧ ∀ x ∈ S, ∀ y ∈ H, D.Adj x y → y ∈ S) have hH_mem : H ∈ closed_subsets := by rw [Finset.mem_filter] refine ⟨Finset.mem_powerset_self H, hne, fun x hx y hy _ => hy⟩ have hcs_ne : closed_subsets.Nonempty := ⟨H, hH_mem⟩ obtain ⟨T, hT_mem, hT_min⟩ := Finset.exists_min_image closed_subsets Finset.card hcs_ne rw [Finset.mem_filter, Finset.mem_powerset] at hT_mem rcases hT_mem with ⟨hTH, hTne, hTclosed⟩ refine ⟨T, hTH, hTne, hTclosed, ?_⟩
For any u ∈ T, the set R_u of vertices in T reachable from u along paths in T is a nonempty subset of T.
To show T is strongly connected, let u, v ∈ T. We define R_u as the set of vertices w ∈ T reachable from u by a directed path in T. The singleton path [u] shows u ∈ R_u, so R_u is nonempty. By definition, R_u ⊆ T ⊆ H.
uses
Finset.mem_filter,digraph_is_directed_path_singleton,List.mem_singleton,Finset.filter_subsetintro u hu v hv let R_u := T.filter (fun w => ∃ p : List α, digraph_is_directed_path D p u w ∧ ∀ z ∈ p, z ∈ T) have hu_Ru : u ∈ R_u := by rw [Finset.mem_filter] refine ⟨hu, [u], digraph_is_directed_path_singleton D u, ?_⟩ intro z hz simp only [List.mem_singleton] at hz subst hz exact hu have hRu_ne : R_u.Nonempty := ⟨u, hu_Ru⟩ have hRu_sub_T : R_u ⊆ T := Finset.filter_subset _ _ have hRu_sub_H : R_u ⊆ H := hRu_sub_T.trans hTH
The reachable set R_u is closed under outgoing edges to H.
If x ∈ R_u and y ∈ H with D.Adj x y, then y ∈ T because x ∈ T and T is closed under outgoing edges to H. Since x ∈ R_u, there is a path p in T from u to x. Applying the helper lemma digraph_finite_sink_strong_subgraph_path_extend_or_prefix to p and the edge x → y yields a directed path q in T from u to y, proving y ∈ R_u.
uses
Finset.mem_filter,digraph_finite_sink_strong_subgraph_path_extend_or_prefixhave hRu_closed : ∀ x ∈ R_u, ∀ y ∈ H, D.Adj x y → y ∈ R_u := by intro x hx y hy hadj rw [Finset.mem_filter] at hx rcases hx with ⟨hxT, p, hp, hpT⟩ have hyT : y ∈ T := hTclosed x hxT y hy hadj obtain ⟨q, hq, hqT⟩ := digraph_finite_sink_strong_subgraph_path_extend_or_prefix D T u x y p hp hpT hyT hadj rw [Finset.mem_filter] exact ⟨hyT, q, hq, hqT⟩
T = R_u, so there is a directed path in T from u to v.
Since R_u is a nonempty subset of H closed under outgoing edges into H, it belongs to closed_subsets. By the minimality of |T|, we have |T| ≤ |R_u|. Combined with R_u ⊆ T, this forces T = R_u. In particular, v ∈ R_u, providing the required directed path in T from u to v and establishing that T is strongly connected.
uses
Finset.mem_filter,Finset.mem_powerset,Finset.Subset.antisymm,Finset.eq_of_subset_of_card_le,subset_rflhave hRu_mem : R_u ∈ closed_subsets := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨hRu_sub_H, hRu_ne, hRu_closed⟩ have hcard_le : T.card ≤ R_u.card := hT_min R_u hRu_mem have hT_eq_Ru : T = R_u := Finset.Subset.antisymm (Finset.eq_of_subset_of_card_le hRu_sub_T hcard_le ▸ subset_rfl) hRu_sub_T have hv_Ru : v ∈ R_u := hT_eq_Ru ▸ hv rw [Finset.mem_filter] at hv_Ru exact hv_Ru.2
List.append_of_mem- If an element a belongs to a list l, then l can be decomposed as s ++ a :: t for some lists s and t.
List.nil_append- Appending the empty list to any list as yields as unchanged.
List.head?_cons- The optional head of a nonempty list a :: l is some a.
List.cons_append- Prepending an element a to an appended list as ++ bs equals a :: (as ++ bs).
List.IsChain.append- Concatenating two chains under a relation R yields a chain provided R holds between the last element of the first and the head of the second.
List.IsChain.singleton- A singleton list [a] is always a chain under any relation R.
Option.mem_some_iff- An element a belongs to some b if and only if b = a.
List.nodup_append- A concatenated list l₁ ++ l₂ has no duplicates if and only if each has no duplicates and they are disjoint.
List.nodup_singleton- A singleton list [a] has no duplicates.
List.mem_singleton- An element a belongs to [b] if and only if a = b.
List.head?_append_of_ne_nil- If l₁ is nonempty, the head of l₁ ++ l₂ equals the head of l₁.
List.getLast?_append_cons- The last element of l₁ ++ a :: l₂ is equal to the last element of a :: l₂.
List.mem_append- An element belongs to s ++ t if and only if it belongs to s or to t.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_powerset_self- Every finite set s is an element of its own powerset.
Finset.exists_min_image- Every nonempty finite set contains an element minimizing a given function into a linearly ordered type.
Finset.mem_powerset- A finite set s belongs to the powerset of t if and only if s ⊆ t.
digraph_is_directed_path_singleton- For any vertex v in a digraph D, the singleton list [v] is a directed path from v to v.
Finset.filter_subset- Filtering a finite set s produces a subset of s.
digraph_finite_sink_strong_subgraph_path_extend_or_prefix- If there is a directed path in T from u to x, an edge from x to y, and y ∈ T, then there is a directed path in T from u to y.
Finset.Subset.antisymm- If two finite sets are subsets of each other, they are equal.
Finset.eq_of_subset_of_card_le- If s ⊆ t and t has cardinality at most that of s, then s = t.
subset_rfl- Every set is a subset of itself.
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.
lemma digraph_finite_sink_strong_subgraph_path_extend_or_prefix {α : Type*} [DecidableEq α] (D : Digraph α) (T : Finset α) (u x y : α) (p : List α) (hp : digraph_is_directed_path D p u x) (hpT : ∀ z ∈ p, z ∈ T) (hyT : y ∈ T) (hadj : D.Adj x y) : ∃ q : List α, digraph_is_directed_path D q u y ∧ ∀ z ∈ q, z ∈ T := by by_cases hy : y ∈ p · obtain ⟨l₁, l₂, rfl⟩ := List.append_of_mem hy have hpref : l₁ ++ [y] <+: l₁ ++ y :: l₂ := ⟨l₂, by simp⟩ refine ⟨l₁ ++ [y], ⟨?_, ?_, ?_, ?_⟩, ?_⟩ · exact hp.1.prefix hpref · exact hp.2.1.sublist hpref.sublist · cases l₁ with | nil => simp only [List.nil_append, List.head?_cons] at hp ⊢ exact hp.2.2.1 | cons w ws => simp only [List.cons_append, List.head?_cons] at hp ⊢ exact hp.2.2.1 · simp · intro z hz exact hpT z (hpref.subset hz) · rcases hp with ⟨hchain, hnodup, hhead, hlast⟩ have hp_ne : p ≠ [] := by rintro rfl simp at hhead refine ⟨p ++ [y], ⟨?_, ?_, ?_, ?_⟩, ?_⟩ · apply List.IsChain.append hchain (List.IsChain.singleton y) intro a ha b hb simp only [hlast, Option.mem_some_iff] at ha simp only [List.head?_cons, Option.mem_some_iff] at hb subst ha hb exact hadj · rw [List.nodup_append] refine ⟨hnodup, List.nodup_singleton y, ?_⟩ intro a ha b hb simp only [List.mem_singleton] at hb subst hb rintro rfl exact hy ha · rw [List.head?_append_of_ne_nil _ hp_ne] exact hhead · rw [List.getLast?_append_cons] simp · intro z hz simp only [List.mem_append, List.mem_singleton] at hz rcases hz with hz | rfl · exact hpT z hz · exact hyTtheorem digraph_finite_sink_strong_subgraph (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (H : Finset α) (hne : H.Nonempty) : ∃ T : Finset α, T ⊆ H ∧ T.Nonempty ∧ (∀ x ∈ T, ∀ y ∈ H, D.Adj x y → y ∈ T) ∧ (∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) := by classical let closed_subsets : Finset (Finset α) := H.powerset.filter (fun S => S.Nonempty ∧ ∀ x ∈ S, ∀ y ∈ H, D.Adj x y → y ∈ S) have hH_mem : H ∈ closed_subsets := by rw [Finset.mem_filter] refine ⟨Finset.mem_powerset_self H, hne, fun x hx y hy _ => hy⟩ have hcs_ne : closed_subsets.Nonempty := ⟨H, hH_mem⟩ obtain ⟨T, hT_mem, hT_min⟩ := Finset.exists_min_image closed_subsets Finset.card hcs_ne rw [Finset.mem_filter, Finset.mem_powerset] at hT_mem rcases hT_mem with ⟨hTH, hTne, hTclosed⟩ refine ⟨T, hTH, hTne, hTclosed, ?_⟩ intro u hu v hv let R_u := T.filter (fun w => ∃ p : List α, digraph_is_directed_path D p u w ∧ ∀ z ∈ p, z ∈ T) have hu_Ru : u ∈ R_u := by rw [Finset.mem_filter] refine ⟨hu, [u], digraph_is_directed_path_singleton D u, ?_⟩ intro z hz simp only [List.mem_singleton] at hz subst hz exact hu have hRu_ne : R_u.Nonempty := ⟨u, hu_Ru⟩ have hRu_sub_T : R_u ⊆ T := Finset.filter_subset _ _ have hRu_sub_H : R_u ⊆ H := hRu_sub_T.trans hTH have hRu_closed : ∀ x ∈ R_u, ∀ y ∈ H, D.Adj x y → y ∈ R_u := by intro x hx y hy hadj rw [Finset.mem_filter] at hx rcases hx with ⟨hxT, p, hp, hpT⟩ have hyT : y ∈ T := hTclosed x hxT y hy hadj obtain ⟨q, hq, hqT⟩ := digraph_finite_sink_strong_subgraph_path_extend_or_prefix D T u x y p hp hpT hyT hadj rw [Finset.mem_filter] exact ⟨hyT, q, hq, hqT⟩ have hRu_mem : R_u ∈ closed_subsets := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨hRu_sub_H, hRu_ne, hRu_closed⟩ have hcard_le : T.card ≤ R_u.card := hT_min R_u hRu_mem have hT_eq_Ru : T = R_u := Finset.Subset.antisymm (Finset.eq_of_subset_of_card_le hRu_sub_T hcard_le ▸ subset_rfl) hRu_sub_T have hv_Ru : v ∈ R_u := hT_eq_Ru ▸ hv rw [Finset.mem_filter] at hv_Ru exact hv_Ru.2