AFTD Auto-Formalizing Theoretical Domains

digraph_finite_sink_strong_subgraph

theoremverified

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
Used by 2

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.

  1. 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.

    lines 7–22

    uses List.append_of_mem, List.nil_append, List.head?_cons, List.cons_append

      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)
  2. 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.

    lines 23–49

    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
  3. 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.

    lines 58–68

    uses Finset.mem_filter, Finset.mem_powerset_self, Finset.exists_min_image, Finset.mem_powerset

      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, ?_⟩
  4. 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.

    lines 69–80

    uses Finset.mem_filter, digraph_is_directed_path_singleton, List.mem_singleton, Finset.filter_subset

      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
  5. 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.

    lines 81–89

    uses Finset.mem_filter, digraph_finite_sink_strong_subgraph_path_extend_or_prefix

      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⟩
  6. 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.

    lines 90–99

    uses Finset.mem_filter, Finset.mem_powerset, Finset.Subset.antisymm, Finset.eq_of_subset_of_card_le, subset_rfl

      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
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

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
See it in the graphDiscuss this resultChallenge it