AFTD Auto-Formalizing Theoretical Domains

digraph_common_cycle_core_excludes_high_degree_vertices

theoremverified

Suppose a finite vertex set T is covered by R and P, P has at most k minus two vertices, every directed cycle in T contains a nonempty set S, every vertex of T has at most one outneighbor in S, and every vertex of T in R outside S has at least k outneighbors in T. Then T is disjoint from R outside S.

Statement

theorem digraph_common_cycle_core_excludes_high_degree_vertices
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (T R S P : Finset α) (k : ℕ) (hloop : ∀ x, ¬ D.Adj x x)
    (hne : S.Nonempty) (hcover : T ⊆ R ∪ P) (hP : P.card + 2 ≤ k)
    (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C)
    (huniq : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1)
    (hdeg : ∀ x ∈ T, x ∈ R → x ∉ S → k ≤ (T.filter fun y => D.Adj x y).card) :
    Disjoint T (R \ S)
Source
Common-cycle core counting for the oriented twenty-cut profile.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • digraph_low_cut_contains_cycleIn a finite loopless digraph with minimum outdegree at least r, a vertex set of at least r vertices contains a directed cycle if fewer…
Used by 2

The proof, explained

To show that T and R \ S are disjoint, the proof considers their intersection X = T ∩ (R \ S) and shows it is empty by contradiction. If X were nonempty, counting outneighbors shows that every vertex in X has at least one outneighbor inside X, because its outdegree in T is at least k, while S absorbs at most 1 outneighbor and P contains at most k - 2 vertices. In a finite loopless digraph, such a subset must contain a directed cycle C ⊆ X ⊆ T. However, by hypothesis every cycle in T contains the nonempty set S, which forces S ⊆ X and directly contradicts the fact that X contains no elements of S.

  1. Define the candidate intersection set X = T ∩ (R \ S).

    We enable classical reasoning and introduce X as the set of vertices in T that belong to R but not to S. Disjointness of T and R \ S is equivalent to showing that X is empty.

    lines 12–13

      classical
      let X := T ∩ (R \ S)
  2. Every vertex in X has at least one outneighbor in X.

    Fix x ∈ X; then x ∈ T, x ∈ R, and x ∉ S. Let I, A, and B be the sets of outneighbors of x in T, X, and S, respectively. Since T ⊆ R ∪ P, every outneighbor y ∈ I lies in S (so y ∈ B), in P, or in R \ S (which places y in X = T ∩ (R \ S) since y ∈ T, so y ∈ A). Hence I ⊆ (A ∪ B) ∪ P. By subadditivity of cardinalities, |I| ≤ |A| + |B| + |P|. But x ∈ R \ S has outdegree at least k in T (|I| ≥ k), at most 1 outneighbor in S (|B| ≤ 1), and |P| ≤ k - 2. Linear arithmetic (omega) then forces |A| ≥ |I| - |B| - |P| ≥ k - 1 - (k - 2) = 1.

    lines 14–42

    uses Finset.mem_inter.mp, Finset.mem_sdiff.mp, Finset.mem_filter.mp, Finset.mem_union_left, Finset.mem_union_right, Finset.mem_filter.mpr, Finset.mem_union.mp, Finset.mem_inter.mpr, Finset.mem_sdiff.mpr, Finset.card_le_card, Finset.card_union_le

      have hout : ∀ x ∈ X, 1 ≤ (X.filter fun y => D.Adj x y).card := by
        intro x hx
        have hxT : x ∈ T := (Finset.mem_inter.mp hx).1
        have hxR : x ∈ R := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).1
        have hxS : x ∉ S := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).2
        let I := T.filter fun y => D.Adj x y
        let A := X.filter fun y => D.Adj x y
        let B := S.filter fun y => D.Adj x y
        have hsub : I ⊆ (A ∪ B) ∪ P := by
          intro y hy
          have hyT := (Finset.mem_filter.mp hy).1
          have hyD := (Finset.mem_filter.mp hy).2
          have hyRP := hcover hyT
          by_cases hyS : y ∈ S
          · apply Finset.mem_union_left
            apply Finset.mem_union_right
            exact Finset.mem_filter.mpr ⟨hyS,hyD⟩
          · rcases Finset.mem_union.mp hyRP with hyR | hyP
            · apply Finset.mem_union_left
              apply Finset.mem_union_left
              exact Finset.mem_filter.mpr ⟨Finset.mem_inter.mpr ⟨hyT,Finset.mem_sdiff.mpr ⟨hyR,hyS⟩⟩,hyD⟩
            · exact Finset.mem_union_right _ hyP
        have h1 := Finset.card_le_card hsub
        have h2 := Finset.card_union_le (A ∪ B) P
        have h3 := Finset.card_union_le A B
        have h4 : B.card ≤ 1 := huniq x hxT
        have h5 : k ≤ I.card := hdeg x hxT hxR hxS
        change 1 ≤ A.card
        omega
  3. The set X is empty.

    Suppose for contradiction that X is nonempty. Since every vertex in X has an outneighbor in X, the graph has no self-loops, and α is finite, the lemma digraph_low_cut_contains_cycle_outdeg_cycle provides a directed cycle C entirely contained in X. Because X ⊆ T, C is a directed cycle in T, so by assumption hcore, the set S must be a subset of C. Since S is nonempty, choosing any s ∈ S yields s ∈ C ⊆ X. But every element of X lies outside S by definition of X = T ∩ (R \ S), giving s ∉ S, which is a contradiction.

    lines 43–58

    uses Finset.nonempty_iff_ne_empty.mpr, Finset.card_pos.mp, Finset.mem_filter.mp, digraph_low_cut_contains_cycle_outdeg_cycle, Finset.mem_inter.mp, Finset.mem_sdiff.mp

      have hX : X = ∅ := by
        by_contra hh
        have hXne : X.Nonempty := Finset.nonempty_iff_ne_empty.mpr hh
        have hsuccessor : ∀ x ∈ X, ∃ y ∈ X, D.Adj x y := by
          intro x hx
          obtain ⟨y,hy⟩ := Finset.card_pos.mp (by have := hout x hx; omega :
            0 < (X.filter fun y => D.Adj x y).card)
          exact ⟨y,(Finset.mem_filter.mp hy).1,(Finset.mem_filter.mp hy).2⟩
        obtain ⟨C,hCX,hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hXne hsuccessor
        have hCT : C ⊆ T := by
          intro x hx
          exact (Finset.mem_inter.mp (hCX hx)).1
        have hSC := hcore C hCT hcyc
        obtain ⟨s,hs⟩ := hne
        have hsX := hCX (hSC hs)
        exact (Finset.mem_sdiff.mp (Finset.mem_inter.mp hsX).2).2 hs
  4. T and R \ S are disjoint.

    Any element in both T and R \ S would lie in their intersection X. Since X = ∅, no such element exists, proving that T and R \ S are disjoint.

    lines 59–63

    uses Finset.disjoint_left.mpr, Finset.mem_inter.mpr

      apply Finset.disjoint_left.mpr
      intro x hxT hxRS
      have hx : x ∈ X := Finset.mem_inter.mpr ⟨hxT,hxRS⟩
      rw [hX] at hx
      simpa using hx
digraph_low_cut_contains_cycle_outdeg_cycle
In a finite loopless directed graph, if a nonempty subset of vertices has every vertex possessing an outneighbor in the subset, then the subset contains a directed cycle.
Finset.card_le_card
A finite subset has cardinality at most that of its superset.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their individual cardinalities.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp
An element of a filtered set belongs to the original set and satisfies the filtering condition.
Finset.mem_filter.mpr
An element that belongs to a set and satisfies a predicate belongs to the filtered set.
Finset.mem_inter.mp
An element of an intersection belongs to both sets.
Finset.mem_inter.mpr
An element belonging to both sets belongs to their intersection.
Finset.mem_sdiff.mp
An element of a set difference belongs to the first set and not to the second.
Finset.mem_sdiff.mpr
An element that belongs to the first set and not the second belongs to their set difference.
Finset.mem_union.mp
An element of a union belongs to at least one of the sets.
Finset.mem_union_left
An element belonging to the first set of a union belongs to the union.
Finset.mem_union_right
An element belonging to the second set of a union belongs to the union.
Finset.nonempty_iff_ne_empty.mpr
A set that is not equal to the empty set is nonempty.

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

set_option maxHeartbeats 3000000set_option maxRecDepth 4096theorem digraph_common_cycle_core_excludes_high_degree_vertices    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (T R S P : Finset α) (k : ℕ) (hloop : ∀ x, ¬ D.Adj x x)    (hne : S.Nonempty) (hcover : T ⊆ R ∪ P) (hP : P.card + 2 ≤ k)    (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C)    (huniq : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1)    (hdeg : ∀ x ∈ T, x ∈ R → x ∉ S → k ≤ (T.filter fun y => D.Adj x y).card) :    Disjoint T (R \ S) := by  classical  let X := T ∩ (R \ S)  have hout : ∀ x ∈ X, 1 ≤ (X.filter fun y => D.Adj x y).card := by    intro x hx    have hxT : x ∈ T := (Finset.mem_inter.mp hx).1    have hxR : x ∈ R := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).1    have hxS : x ∉ S := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).2    let I := T.filter fun y => D.Adj x y    let A := X.filter fun y => D.Adj x y    let B := S.filter fun y => D.Adj x y    have hsub : I ⊆ (A ∪ B) ∪ P := by      intro y hy      have hyT := (Finset.mem_filter.mp hy).1      have hyD := (Finset.mem_filter.mp hy).2      have hyRP := hcover hyT      by_cases hyS : y ∈ S      · apply Finset.mem_union_left        apply Finset.mem_union_right        exact Finset.mem_filter.mpr ⟨hyS,hyD⟩      · rcases Finset.mem_union.mp hyRP with hyR | hyP        · apply Finset.mem_union_left          apply Finset.mem_union_left          exact Finset.mem_filter.mpr ⟨Finset.mem_inter.mpr ⟨hyT,Finset.mem_sdiff.mpr ⟨hyR,hyS⟩⟩,hyD⟩        · exact Finset.mem_union_right _ hyP    have h1 := Finset.card_le_card hsub    have h2 := Finset.card_union_le (A ∪ B) P    have h3 := Finset.card_union_le A B    have h4 : B.card ≤ 1 := huniq x hxT    have h5 : k ≤ I.card := hdeg x hxT hxR hxS    change 1 ≤ A.card    omega  have hX : X = ∅ := by    by_contra hh    have hXne : X.Nonempty := Finset.nonempty_iff_ne_empty.mpr hh    have hsuccessor : ∀ x ∈ X, ∃ y ∈ X, D.Adj x y := by      intro x hx      obtain ⟨y,hy⟩ := Finset.card_pos.mp (by have := hout x hx; omega :        0 < (X.filter fun y => D.Adj x y).card)      exact ⟨y,(Finset.mem_filter.mp hy).1,(Finset.mem_filter.mp hy).2⟩    obtain ⟨C,hCX,hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hXne hsuccessor    have hCT : C ⊆ T := by      intro x hx      exact (Finset.mem_inter.mp (hCX hx)).1    have hSC := hcore C hCT hcyc    obtain ⟨s,hs⟩ := hne    have hsX := hCX (hSC hs)    exact (Finset.mem_sdiff.mp (Finset.mem_inter.mp hsX).2).2 hs  apply Finset.disjoint_left.mpr  intro x hxT hxRS  have hx : x ∈ X := Finset.mem_inter.mpr ⟨hxT,hxRS⟩  rw [hX] at hx  simpa using hx
See it in the graphDiscuss this resultChallenge it