digraph_common_predecessor_graph
def
The simple graph joining distinct vertices that have a common in-neighbor in the digraph.
Statement
def digraph_common_predecessor_graph {α : Type} (D : Digraph α) : SimpleGraph α
- Source
- Auxiliary graph in arXiv:2610.11517, Proposition 4.3, and the four-cycle minimum-counterexample route.
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 47
- digraph_common_predecessor_graph_connectedIn a nonempty loopless strongly connected digraph in which every arc has a common in-neighbor, the common-predecessor graph is connected.
- digraph_trianglefree_deficit_sharp54_certificateThe displayed 54-vertex digraph is loopless, oriented, triangle-free, and arc-dominated. Its total positive outdegree-minus-indegree…
- 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_two_common_parents_edge_multiplicityTwo distinct vertices with two distinct common predecessors form an edge in the common-predecessor graph with multiplicity at least two.
- digraph_oriented_degree_deficit_overlap_budgetIn every finite loopless oriented arc-dominated digraph, twice the sum of positive outdegree-minus-indegree deficits is at most three…
- digraph_common_predecessor_degree_le_indegree_mulIn an r-outregular finite digraph, the degree of a vertex in the common-predecessor graph is at most (r−1) times its directed indegree.
- digraph_common_predecessor_graph_edge_count_leIf every vertex of a finite digraph has at most seven out-neighbors, then its common-predecessor graph has at most 21 times as many edges…
- digraph_seven_two_overlap_order_ge_43A finite digraph with every outdegree at least seven and twice its common-predecessor overlap below its order has at least 43 vertices.
- digraph_twenty_profile_overlap_cardinality_boundIf five vertices of a finite part have internal outdegrees 1 through 5 and all other part vertices have internal outdegree seven, the…
- 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_common_predecessor_graph_129_contradictionNo digraph on 129 vertices can have outdegree at most seven while its common-predecessor graph is connected and has no independent set of…
- 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_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- 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_126_near_linear_clean_small_indegreeIf a 7-outregular digraph on 126 vertices has at least 2629 common-predecessor edges, it has a vertex of indegree at most nine such that…
- 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_two_overlap_good_center_counterexampleThe displayed thirteen-vertex graph is loopless, oriented and arc-dominated, has common-predecessor overlap six, and has no vertex whose…
- digraph_nested_parents_overlap_generalFor k transitive low vertices pointing to q, nested common-predecessor counts k+3−t force common-predecessor overlap at least twice…
- 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_common_predecessor_edge_le_sum_chooseThe common-predecessor graph has at most the sum over vertices of the number of pairs in each out-neighborhood.
- digraph_127_regular_independence_small_overlapA seven-outregular digraph on 127 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- digraph_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
- digraph_128_regular_independence_small_overlapA seven-outregular digraph on 128 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- digraph_weighted_center_strict54_certificateThe displayed 54-vertex graph is loopless, oriented, triangle-free and arc-dominated, has minimum outdegree seven and auxiliary…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_common_predecessor_girth_correctionThe sum, over common-predecessor edges of multiplicity at least two, of the positive part of g+1 minus twice the number of common…
- digraph_common_predecessor_seven_bounded_indegree_degree_boundIf all outdegrees equal seven and all indegrees are at most seven, every vertex of the common-predecessor graph has degree at most 42.
- 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_common_predecessor_vertex_incidence_boundFor an r-outregular finite digraph, the number of common-predecessor edge incidences repeated at a given vertex is at most the total…
- digraph_129_regular_independence_small_overlapA seven-outregular digraph on 129 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- digraph_two_overlap_good_center_criterion_falseIt is false that every oriented arc-dominated loopless digraph on thirteen vertices with twice its common-predecessor overlap below…
- 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_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_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_common_predecessor_edges_seven_cliqueIn a 7-outregular finite digraph, every edge of its common-predecessor graph lies in a clique of exactly seven vertices.
- 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_common_predecessor_balanced_seven_card_le_121A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has…
- 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_arc_choice_collision_repeated_pairWhen two outgoing arcs of a loopless digraph receive the same chosen common predecessor, their distinct heads form an auxiliary edge with…
- digraph_common_predecessor_double_edgesThe number of edges in the common-predecessor graph whose endpoints have exactly two common predecessors.
- 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…
- 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_oriented_small_overlap_good_centerIn an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has…
- digraph_arc_domination_overlap_indegree_deficit_boundIn an oriented loopless r-outregular arc-dominated digraph, the total shortfall of indegrees below r is at most choose(z+1,2), where z is…
- 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_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_common_predecessor_graph {α : Type} (D : Digraph α) : SimpleGraph α := { Adj := fun u v => u ≠ v ∧ ∃ w, D.Adj w u ∧ D.Adj w v symm := by constructor intro u v h obtain ⟨hne, w, hwu, hwv⟩ := h exact ⟨hne.symm, w, hwv, hwu⟩ loopless := by constructor intro u h exact h.1 rfl }