AFTD Auto-Formalizing Theoretical Domains

digraph_common_cycle_core_outside_injection

theoremverified

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

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.

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

    lines 13–14

    uses digraph_common_cycle_core_neighbor_unique

      classical
      have hu := digraph_common_cycle_core_neighbor_unique α D T K hKT hloop hstrong hcore
  2. Every 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.

    lines 15–31

    uses Finset.mem_filter.mp, Finset.mem_sdiff.mpr, Finset.mem_filter.mpr, Finset.card_le_card

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

    lines 32–33

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

    lines 34–47

    uses Subtype.ext, congrArg, Finset.mem_sdiff.mp, Finset.card_le_one.mp, Finset.mem_filter.mpr

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

    lines 48–49

    uses Fintype.card_le_of_injective

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

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