digraph_directed_cycle_on
def
s 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 next and the last with an arc back to the first (a digon counts).
Statement
def digraph_directed_cycle_on {α : Type} [DecidableEq α] (D : Digraph α) (s : Finset α) : Prop
- Source
- Filed by the prover as a step towards another result
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 59
- digraph_three_large_parts_no_four_cycles_cross_ge_forty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- digraph_four_cycles_from_two_cycles_few_badTwo disjoint directed cycles with nonempty remainder can be extended to four under the displayed robust two-cycle condition if each…
- digraph_safe17_four_cycle_unsafeNo directed four-cycle in the displayed graph is safe for deletion with a two-neighbor budget.
- digraph_linear_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem at outdegree d+2 for oriented linear arc-dominated digraphs.
- digraph_17_shared_target_forces_two_cyclesThe normalized oriented seventeen-vertex shared-target configuration with three designated parents contains two disjoint cycles, assuming…
- 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_four_cycles_from_small_cutIn a loopless digraph of minimum outdegree seven, if B is nonempty and all arcs leaving B end in a set S of at most two vertices, a…
- digraph_girth_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- digraph_cycle_packing_from_small_directed_cutA nonempty directed block with at most two vertices in its outgoing boundary contains s disjoint directed cycles under the stated s-cycle…
- digraph_common_cycle_core_excludes_high_degree_verticesSuppose 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…
- digraph_oriented_cut20_sharp_example_certificateThe explicit oriented example has a seven-outregular twenty-vertex part with twenty outgoing arcs and no two disjoint cycles; every…
- digraph_twenty_cut_degree_profile_under_two_cycle_sequencesFor a seven-outregular two-cycle-free part with a twenty-arc outgoing cut, the displayed robust and two-cycle degree-sequence criteria…
- digraph_safe_cycle_universal_criterion_falseIt is false that every loopless oriented seven-diregular graph on seventeen vertices with a complete common-predecessor graph contains a…
- digraph_trianglefree_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- digraph_seven_out_robust_cut_thresholdsUnder the displayed robust two-cycle criterion, if a set of at least seven vertices in a digraph of minimum outdegree seven contains no…
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
- digraph_safe17_triangle_cycle_unsafeNo directed triangle in the displayed graph is safe for deletion with a two-neighbor budget.
- digraph_finite_predecessor_closed_set_cycleA nonempty finite predecessor-closed subset of a loopless digraph contains a directed cycle.
- digraph_safe17_two_cycle_impossibleThe displayed oriented graph has no directed cycle on two vertices.
- digraph_common_predecessor_graph_indep_free_fourIf each in-neighborhood of a finite digraph contains a directed cycle and the digraph has no four disjoint directed cycles, then its…
- digraph_four_cycles_from_digon_and_three_cycle_theoremIf a finite loopless digraph has minimum outdegree seven, contains a directed two-cycle, and every nonempty vertex subset whose induced…
- digraph_short_parent_set_not_all_chargedIn a loopless digraph of directed girth at least g, a nonempty common-predecessor set with fewer than g members cannot have every parent…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles, its vertices are partitioned into three parts of size…
- digraph_trianglefree_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
- digraph_digon_cycle_packing_stepA directed two-cycle can be added to any k-cycle packing theorem two outdegree units lower.
- digraph_seven_out_robust_two_cycle_free_cut_ge_twentyA set of at least seven vertices in a digraph of minimum outdegree seven, containing no two disjoint directed cycles, has at least twenty…
- 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…
- digraph_robust_pair_source16_certificateThe explicit sixteen-vertex graph is loopless and oriented, has minimum outdegree seven and auxiliary independence at most two, and has…
- digraph_general_robust_two_cycle_free_cutAssuming the displayed robust two-cycle criterion, every two-cycle-free part of size at least d in a graph with outdegree at least d on…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- digraph_safe17_every_proper_cycle_unsafeEvery proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.
- digraph_small_overlap_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_dominated_arcs_in_neighborhood_cycleIn a finite loopless digraph where every vertex has positive outdegree and every arc has a common in-neighbor, the in-neighborhood of…
- digraph_local_outneighborhood_cycleIf an out-neighborhood is nonempty and each of its vertices has an out-neighbor inside it, it contains a directed cycle.
- digraph_oriented_girth_degree_deficit_overlap_budgetIn a finite loopless oriented arc-dominated digraph whose directed cycles have at least g vertices, with g at least three, g−1 times the…
- digraph_suppress_to_two_cycles_liftIf x has an arc to q, every pair of vertex-disjoint cycles after suppressing x into q lifts to a disjoint pair in the original digraph.
- digraph_127_four_cycles_under_extremal_and_cycle_criteriaA 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed…
- digraph_oriented_regular_cut20_extension_certificateThe extended example is oriented, seven-outregular, arc-dominated and strongly connected, with a twenty-vertex part of cut twenty and no…
- digraph_balanced_seven_large_forces_four_cycles_conditionalA strongly connected loopless 7-outregular digraph on at least 122 vertices whose indegrees are at most seven has four disjoint directed…
- digraph_four_cycles_two_triangles_few_badSuppose a finite loopless digraph has minimum outdegree at least seven and contains two disjoint directed triangles. If no outside vertex…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- digraph_oriented_robust_cut_twenty_one_counterexampleLet D be digraph_oriented_cut20_sharp_example on Fin 26 and B the set of vertices with value less than 20. D is oriented; B has at least…
- digraph_16_shared_target_forces_two_cyclesThe normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.
- digraph_common_cycle_core_outside_injectionIn 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…
- digraph_cut20_sharp_example_certificateIn the displayed 20-vertex graph, the first 13 vertices all have outdegree seven, exactly 20 arcs leave that set, and it contains no two…
- digraph_two_cycles_boundary_obstructionIf a digraph of minimum outdegree seven has no four disjoint cycles, then for any two disjoint cycles with nonempty remainder either some…
- digraph_robust_cut_twenty_one_counterexampleLet D be digraph_cut20_sharp_example on Fin 20 and let B be the vertices with value below 13. The set B has at least seven vertices, each…
- digraph_16_shared_target_many_low_arcsIn the displayed oriented sixteen-vertex configuration with no two disjoint cycles, at least four outneighbors of the common target point…
- digraph_packing_free_cut_peeling_boundIf a set of at least r−m+1 vertices contains no q disjoint directed cycles, while every nonempty induced digraph of minimum outdegree m…
- digraph_small_overlap_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2…
- trianglefree24_graph_four_cyclesFour displayed pairwise disjoint four-vertex subsets of the explicit 24-vertex digraph are directed cycles.
- digraph_oriented_cut20_dominated_extension_certificateThe extended example is oriented, strongly connected, has minimum outdegree seven, a seven-outregular twenty-vertex part with cut twenty…
- digraph_126_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains…
- digraph_clean_outneighborhood_cycle_packing_stepA directed cycle inside a clean out-neighborhood can be added to any k-cycle packing theorem two outdegree units lower.
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
- digraph_four_cycles_from_undominated_triangleIf a finite digraph of minimum outdegree at least seven has a directed triangle that no outside vertex dominates and the displayed…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
Lean source view module on GitHub
def digraph_directed_cycle_on {α : Type} [DecidableEq α] (D : Digraph α) (s : Finset α) : Prop := ∃ l : List α, l.Nodup ∧ 2 ≤ l.length ∧ l.toFinset = s ∧ l.IsChain D.Adj ∧ ∃ a b, l.head? = some a ∧ l.getLast? = some b ∧ D.Adj b a