AFTD Auto-Formalizing Theoretical Domains

digraph_common_cycle_core_neighbor_unique

theoremverified

Inside a strongly connected finite set, if every directed cycle contains a fixed core, every vertex has at most one outgoing neighbor and at most one incoming neighbor in that core.

Statement

theorem digraph_common_cycle_core_neighbor_unique
    (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (T S : Finset α) (hST : S ⊆ T)
    (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 → S ⊆ C) :
    ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 ∧
      (S.filter fun y => D.Adj y x).card ≤ 1
Source
Common-cycle core argument for the oriented twenty-cut profile; experiment 26272 checks all oriented graphs through five vertices.
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_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…
Used by 3

The proof, explained

To show that every vertex x ∈ T has at most one outgoing neighbor in the core S, assume for contradiction that x has two distinct outgoing neighbors a, b ∈ S. By strong connectivity, there is a directed path p in T from a to x. If b lies on p, the subpath from b to x closed with the edge x → b gives a directed cycle in T that omits a; if b does not lie on p, the path p closed with x → a gives a directed cycle in T that omits b. Either case contradicts the hypothesis that every directed cycle in T contains the core S. Applying this uniqueness of outgoing neighbors to the reversed digraph immediately yields the dual bound for incoming neighbors.

  1. A directed path with distinct endpoints, together with a closing edge from its end back to its start, forms a directed cycle on its vertex set.

    Deconstructing the directed path yields a duplicate-free chain of vertices starting at a and ending at b. By case analysis on the list of vertices, the path cannot be empty (since its head is a) and cannot have length 1 (since that would force a = b, contradicting a ≠ b), so its length is at least 2. Together with the closing edge from b to a, this satisfies the definition of a directed cycle.

    lines 8–16

      obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath
      have hlen : 2 ≤ p.length := by
        cases p with
        | nil => simp at hhead
        | cons z zs =>
          cases zs with
          | nil => simp_all
          | cons w ws => simp
      exact ⟨p, hnodup, hlen, rfl, hchain, a, b, hhead, hlast, hclose⟩
  2. To show that any vertex x ∈ T has at most one outgoing neighbor in S, it suffices to derive a contradiction from the existence of distinct neighbors a, b ∈ S with x → a and x → b.

    Using Finset.card_le_one.mpr, we assume for contradiction that there exist distinct vertices a, b ∈ S such that D.Adj x a and D.Adj x b hold (extracted via Finset.mem_filter.mp). Since the digraph has no self-loops, x → a implies a ≠ x, and x → b implies b ≠ x.

    lines 26–36

    uses Finset.card_le_one.mpr, Finset.mem_filter.mp

      classical
      intro x hx
      apply Finset.card_le_one.mpr
      intro a ha b hb
      have haS : a ∈ S := (Finset.mem_filter.mp ha).1
      have hbS : b ∈ S := (Finset.mem_filter.mp hb).1
      have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2
      have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2
      by_contra hab
      have hax : a ≠ x := by intro h; subst a; exact (hloop x) hxa
      have hbx : b ≠ x := by intro h; subst b; exact (hloop x) hxb
  3. There exists a directed path p in T from a to x.

    Since a ∈ S ⊆ T and x ∈ T, the strong connectivity hypothesis on T provides a directed path p from a to x entirely contained within T. We decompose p into its chain property, duplicate-free property, head a, and last element x.

    lines 37–38

      obtain ⟨p,hpath,hpT⟩ := hstrong a (hST haS) x hx
      obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath
  4. When b lies on p, the path decomposes into a prefix starting at a followed by a suffix starting at b that does not contain a.

    We split into cases on whether b ∈ p. Using List.mem_iff_append.mp, p can be written as pre ++ b :: tail. If pre were empty, the head of p would be b, forcing a = b, which contradicts a ≠ b. Hence pre = a :: zs. Because p has no duplicates (List.nodup_append.mp), the suffix b :: tail is duplicate-free and cannot contain a.

    lines 39–55

    uses List.mem_iff_append.mp, List.nil_append, List.head?_cons, Option.some.injEq, List.nodup_append.mp

      by_cases hbp : b ∈ p
      · obtain ⟨pre,tail,hp⟩ := List.mem_iff_append.mp hbp
        cases pre with
        | nil =>
          simp only [List.nil_append, List.head?_cons, Option.some.injEq] at hp hhead
          have : a = b := by simpa [hp] using hhead.symm
          exact hab this
        | cons z zs =>
          have hz : z = a := by
            rw [hp] at hhead
            simpa using hhead
          subst z
          have hnodup' : ((a :: zs) ++ b :: tail).Nodup := by simpa [hp] using hnodup
          have hsufnodup : (b :: tail).Nodup := (List.nodup_append.mp hnodup').2.1
          have hnot : a ∉ b :: tail := by
            intro ha'
            exact (List.nodup_append.mp hnodup').2.2 a (by simp) a ha' rfl
  5. When b lies on p, the suffix b :: tail together with x → b forms a directed cycle in T that omits a, contradicting that every cycle contains S.

    The suffix b :: tail inherits the edge chain property from p and ends at x, making it a directed path from b to x. Closing this path with the edge x → b via in833_path_close_cycle yields a directed cycle whose vertices lie in T. By the core hypothesis, this cycle must contain S and therefore must contain a, which contradicts the fact that a is not in b :: tail.

    lines 56–71

    uses List.getLast?_append_cons, in833_path_close_cycle, List.mem_append_right

          have hchain' : ((a :: zs) ++ b :: tail).IsChain D.Adj := by simpa [hp] using hchain
          have hsufchain : (b :: tail).IsChain D.Adj := hchain'.right_of_append
          have hsuflast : (b :: tail).getLast? = some x := by
            rw [hp, List.getLast?_append_cons] at hlast
            exact hlast
          have hsufpath : digraph_is_directed_path D (b :: tail) b x :=
            ⟨hsufchain, hsufnodup, by simp, hsuflast⟩
          have hcycle := in833_path_close_cycle D (b :: tail) b x hsufpath hbx hxb
          have hsub : (b :: tail).toFinset ⊆ T := by
            intro y hy
            have hy' : y ∈ b :: tail := by simpa using hy
            apply hpT y
            rw [hp]
            exact List.mem_append_right _ hy'
          have hc := hcore (b :: tail).toFinset hsub hcycle haS
          exact hnot (by simpa using hc)
  6. When b does not lie on p, closing p with x → a forms a directed cycle in T that omits b, again contradicting the core hypothesis.

    Closing the full path p from a to x with the edge x → a via in833_path_close_cycle yields a directed cycle on the vertices of p, all of which belong to T. By the core hypothesis, this cycle must contain S, and in particular must contain b. But b is not on p, a contradiction. This completes both branches of the case analysis, establishing a = b.

    lines 72–78

    uses in833_path_close_cycle

      · have hcycle := in833_path_close_cycle D p a x ⟨hchain,hnodup,hhead,hlast⟩ hax hxa
        have hsub : p.toFinset ⊆ T := by
          intro y hy
          apply hpT y
          simpa using hy
        have hc := hcore p.toFinset hsub hcycle hbS
        exact hbp (by simpa using hc)
  7. Any directed cycle in the reversed digraph corresponds to a directed cycle in D on the same vertex set.

    Reversing the list of vertices of a cycle in the reversed digraph preserves non-duplication (List.nodup_reverse.mpr), length, and vertex set. By List.isChain_reverse.mpr, an edge chain in the reversed digraph becomes an edge chain in D. The original closing edge connects the reversed endpoints, producing a directed cycle in D.

    lines 84–92

    uses List.nodup_reverse.mpr, List.isChain_reverse.mpr

      obtain ⟨l, hnodup, hlen, hset, hchain, a, b, ha, hb, hab⟩ := h
      refine ⟨l.reverse, ?_, ?_, ?_, ?_, b, a, ?_, ?_, ?_⟩
      · exact List.nodup_reverse.mpr hnodup
      · simpa using hlen
      · simpa using hset
      · exact List.isChain_reverse.mpr hchain
      · simpa using hb
      · simpa using ha
      · exact hab
  8. Every vertex x ∈ T has at most one outgoing neighbor in S.

    Applying the uniqueness lemma in833_core_out_unique directly gives that the number of outgoing neighbors of x in S is at most 1.

    lines 103–104

    uses in833_core_out_unique

      classical
      have hout := in833_core_out_unique α D T S hST hloop hstrong hcore
  9. The reversed digraph E is loopless, strongly connected on T, and every cycle in T contains the core S.

    Digraph E has no loops because D has none. For any u, v ∈ T, reversing a path from v to u in D provides a directed path from u to v in E (using List.isChain_reverse.mpr). Finally, any cycle in E within T reverses via in833_core_reverse_cycle to a cycle in D, which must contain S by the core hypothesis.

    lines 105–122

    uses List.isChain_reverse.mpr, in833_core_reverse_cycle

      let E : Digraph α := ⟨fun u v => D.Adj v u⟩
      have hEloop : ∀ v, ¬ E.Adj v v := hloop
      have hEstrong : ∀ u ∈ T, ∀ v ∈ T,
          ∃ p : List α, digraph_is_directed_path E p u v ∧ ∀ z ∈ p, z ∈ T := by
        intro u hu v hv
        obtain ⟨p,hp,hT⟩ := hstrong v hv u hu
        obtain ⟨hc,hn,hh,hl⟩ := hp
        refine ⟨p.reverse, ?_, ?_⟩
        · refine ⟨?_, by simpa using hn, ?_, ?_⟩
          · exact List.isChain_reverse.mpr hc
          · simpa using hl
          · simpa using hh
        · intro z hz
          apply hT z
          simpa using hz
      have hEcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on E C → S ⊆ C := by
        intro C hsub hc
        exact hcore C hsub (in833_core_reverse_cycle D C hc)
  10. Every vertex x ∈ T has at most one incoming neighbor in S, completing the theorem.

    Applying in833_core_out_unique to the reversed digraph E shows that x has at most one outgoing neighbor in S in E. Since outgoing edges in E correspond to incoming edges in D, x has at most one incoming neighbor in S, which establishes the second conjunction.

    lines 123–126

    uses in833_core_out_unique

      have hin := in833_core_out_unique α E T S hST hEloop hEstrong hEcore
      intro x hx
      refine ⟨hout x hx, ?_⟩
      simpa [E] using hin x hx
Finset.card_le_one.mpr
A finite set has cardinality at most 1 if any two of its elements are equal.
Finset.mem_filter.mp
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filtering predicate.
List.mem_iff_append.mp
An element belongs to a list if and only if the list can be split into a prefix and a suffix around that element.
List.nil_append
Concatenating the empty list to any list yields the original list.
List.head?_cons
The head of a list constructed by prepending an element is that element.
Option.some.injEq
The constructor 'some' is injective on optional values.
List.nodup_append.mp
If the concatenation of two lists has no duplicates, then both lists have no duplicates and they are disjoint.
List.getLast?_append_cons
The last element of a concatenation ending in a non-empty list is the last element of that suffix.
List.mem_append_right
An element belonging to a suffix also belongs to the concatenated list.
in833_path_close_cycle
A directed path with distinct endpoints, together with a closing edge from end to start, forms a directed cycle on its vertex set.
List.nodup_reverse.mpr
Reversing a list preserves the property of having no duplicate elements.
List.isChain_reverse.mpr
A chain under a relation reverses to a chain under the transposed relation.
in833_core_reverse_cycle
A directed cycle in the reversed digraph on a vertex set is also a directed cycle in the original digraph on that set.
in833_core_out_unique
Inside a strongly connected subset of a loopless digraph where every cycle contains a core S, every vertex has at most one outgoing neighbor in S.

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 4096private theorem in833_path_close_cycle {α : Type} [DecidableEq α]    (D : Digraph α) (p : List α) (a b : α)    (hpath : digraph_is_directed_path D p a b) (hne : a ≠ b) (hclose : D.Adj b a) :    digraph_directed_cycle_on D p.toFinset := by  obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath  have hlen : 2 ≤ p.length := by    cases p with    | nil => simp at hhead    | cons z zs =>      cases zs with      | nil => simp_all      | cons w ws => simp  exact ⟨p, hnodup, hlen, rfl, hchain, a, b, hhead, hlast, hclose⟩private theorem in833_core_out_unique    (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (T S : Finset α) (hST : S ⊆ T)    (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 → S ⊆ C) :    ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 := by  classical  intro x hx  apply Finset.card_le_one.mpr  intro a ha b hb  have haS : a ∈ S := (Finset.mem_filter.mp ha).1  have hbS : b ∈ S := (Finset.mem_filter.mp hb).1  have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2  have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2  by_contra hab  have hax : a ≠ x := by intro h; subst a; exact (hloop x) hxa  have hbx : b ≠ x := by intro h; subst b; exact (hloop x) hxb  obtain ⟨p,hpath,hpT⟩ := hstrong a (hST haS) x hx  obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath  by_cases hbp : b ∈ p  · obtain ⟨pre,tail,hp⟩ := List.mem_iff_append.mp hbp    cases pre with    | nil =>      simp only [List.nil_append, List.head?_cons, Option.some.injEq] at hp hhead      have : a = b := by simpa [hp] using hhead.symm      exact hab this    | cons z zs =>      have hz : z = a := by        rw [hp] at hhead        simpa using hhead      subst z      have hnodup' : ((a :: zs) ++ b :: tail).Nodup := by simpa [hp] using hnodup      have hsufnodup : (b :: tail).Nodup := (List.nodup_append.mp hnodup').2.1      have hnot : a ∉ b :: tail := by        intro ha'        exact (List.nodup_append.mp hnodup').2.2 a (by simp) a ha' rfl      have hchain' : ((a :: zs) ++ b :: tail).IsChain D.Adj := by simpa [hp] using hchain      have hsufchain : (b :: tail).IsChain D.Adj := hchain'.right_of_append      have hsuflast : (b :: tail).getLast? = some x := by        rw [hp, List.getLast?_append_cons] at hlast        exact hlast      have hsufpath : digraph_is_directed_path D (b :: tail) b x :=        ⟨hsufchain, hsufnodup, by simp, hsuflast⟩      have hcycle := in833_path_close_cycle D (b :: tail) b x hsufpath hbx hxb      have hsub : (b :: tail).toFinset ⊆ T := by        intro y hy        have hy' : y ∈ b :: tail := by simpa using hy        apply hpT y        rw [hp]        exact List.mem_append_right _ hy'      have hc := hcore (b :: tail).toFinset hsub hcycle haS      exact hnot (by simpa using hc)  · have hcycle := in833_path_close_cycle D p a x ⟨hchain,hnodup,hhead,hlast⟩ hax hxa    have hsub : p.toFinset ⊆ T := by      intro y hy      apply hpT y      simpa using hy    have hc := hcore p.toFinset hsub hcycle hbS    exact hbp (by simpa using hc)private theorem in833_core_reverse_cycle {α : Type} [DecidableEq α]    (D : Digraph α) (C : Finset α)    (h : digraph_directed_cycle_on ⟨fun u v => D.Adj v u⟩ C) :    digraph_directed_cycle_on D C := by  obtain ⟨l, hnodup, hlen, hset, hchain, a, b, ha, hb, hab⟩ := h  refine ⟨l.reverse, ?_, ?_, ?_, ?_, b, a, ?_, ?_, ?_⟩  · exact List.nodup_reverse.mpr hnodup  · simpa using hlen  · simpa using hset  · exact List.isChain_reverse.mpr hchain  · simpa using hb  · simpa using ha  · exact habtheorem digraph_common_cycle_core_neighbor_unique    (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (T S : Finset α) (hST : S ⊆ T)    (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 → S ⊆ C) :    ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 ∧      (S.filter fun y => D.Adj y x).card ≤ 1 := by  classical  have hout := in833_core_out_unique α D T S hST hloop hstrong hcore  let E : Digraph α := ⟨fun u v => D.Adj v u⟩  have hEloop : ∀ v, ¬ E.Adj v v := hloop  have hEstrong : ∀ u ∈ T, ∀ v ∈ T,      ∃ p : List α, digraph_is_directed_path E p u v ∧ ∀ z ∈ p, z ∈ T := by    intro u hu v hv    obtain ⟨p,hp,hT⟩ := hstrong v hv u hu    obtain ⟨hc,hn,hh,hl⟩ := hp    refine ⟨p.reverse, ?_, ?_⟩    · refine ⟨?_, by simpa using hn, ?_, ?_⟩      · exact List.isChain_reverse.mpr hc      · simpa using hl      · simpa using hh    · intro z hz      apply hT z      simpa using hz  have hEcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on E C → S ⊆ C := by    intro C hsub hc    exact hcore C hsub (in833_core_reverse_cycle D C hc)  have hin := in833_core_out_unique α E T S hST hEloop hEstrong hEcore  intro x hx  refine ⟨hout x hx, ?_⟩  simpa [E] using hin x hx
See it in the graphDiscuss this resultChallenge it