AFTD Auto-Formalizing Theoretical Domains

regular_tournament_five_nearly_doubly_regular

theoremverifiedformalization

The case k = 1 of the conjecture, in a stronger form: every regular tournament of order 5 is nearly doubly regular (any two distinct vertices have at most one common out-neighbour), so in particular every maximizer is.

Statement

theorem regular_tournament_five_nearly_doubly_regular (D : Digraph (Fin 5))
    [DecidableRel D.Adj] (hD : digraph_is_tournament D)
    (hreg : ∀ v, digraph_out_count D v = 2) :
    ∀ i j, i ≠ j → digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1
Formalizes
arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; the order 5 case, checked by computation in the paper
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
  • digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
  • digraph_common_out_countc_ij: the number of common out-neighbours of the vertices i and j of a digraph on Fin n.

The proof, explained

The proof proceeds by ruling out the possibility that two vertices share two common out-neighbours. For any two distinct vertices i and j in a 2-regular tournament, their common out-neighbourhood is contained in the out-neighbourhood of i, which has size 2, so the number of common out-neighbours can only be 0, 1, or 2. If it were 2, cardinality considerations would force the out-neighbourhoods of i and j to be identical. But between any two distinct vertices in a tournament there is an edge in one direction, and either direction would force a self-loop (either j → j or i → i), contradicting irreflexivity.

  1. For any distinct vertices i and j, their common out-neighbourhood is a subset of both N⁺(i) and N⁺(j).

    Fix distinct vertices i and j. By unfolding the definition of the filtered sets using Finset.mem_filter, any vertex w that has directed edges from both i and j is in particular an out-neighbour of i and an out-neighbour of j.

    lines 5–11

    uses Finset.mem_filter

      intro i j hij
      have hsub_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆
          (Finset.filter (fun w => D.Adj i w) Finset.univ) := by
        intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.1⟩
      have hsub_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆
          (Finset.filter (fun w => D.Adj j w) Finset.univ) := by
        intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.2⟩
  2. The number of common out-neighbours of i and j is 0, 1, or 2.

    Because the common out-neighbourhood is contained in N⁺(i), which has size 2 by 2-regularity, its cardinality is at most 2 (Finset.card_le_card). Linear arithmetic over ℕ (omega) then deduces that this count must be 0, 1, or 2.

    lines 12–18

    uses Finset.card_le_card

      have hle : digraph_common_out_count D i j ≤ 2 := by
        have h1 := Finset.card_le_card hsub_i
        have h2 := hreg i
        exact h1.trans_eq h2
      have hcases : digraph_common_out_count D i j = 0 ∨
                    digraph_common_out_count D i j = 1 ∨
                    digraph_common_out_count D i j = 2 := by omega
  3. The cases where the common out-neighbour count is 0 or 1 immediately satisfy the goal.

    A case split on the three possible values leaves only the count 2 to consider, as 0 and 1 satisfy the required disjunction directly.

    lines 19–21

      rcases hcases with h0 | h1 | h2
      · left; exact h0
      · right; exact h1
  4. If the common out-neighbour count were 2, then N⁺(i) and N⁺(j) would be identical.

    Assume for contradiction that the count is 2. Both out-neighbourhoods N⁺(i) and N⁺(j) also have size 2 by regularity. A subset of the same cardinality as the ambient finite set must be the entire set (Finset.eq_of_subset_of_card_le), so both N⁺(i) and N⁺(j) equal their common intersection, hence N⁺(i) = N⁺(j).

    lines 22–36

    uses Finset.eq_of_subset_of_card_le

      · exfalso
        have hcard_comm : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ).card = 2 := h2
        have hcard_i : (Finset.filter (fun w => D.Adj i w) Finset.univ).card = 2 := hreg i
        have hcard_j : (Finset.filter (fun w => D.Adj j w) Finset.univ).card = 2 := hreg j
        have heq_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) =
            (Finset.filter (fun w => D.Adj i w) Finset.univ) := by
          apply Finset.eq_of_subset_of_card_le hsub_i
          rw [hcard_comm, hcard_i]
        have heq_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) =
            (Finset.filter (fun w => D.Adj j w) Finset.univ) := by
          apply Finset.eq_of_subset_of_card_le hsub_j
          rw [hcard_comm, hcard_j]
        have hij_eq : (Finset.filter (fun w => D.Adj i w) Finset.univ) =
            (Finset.filter (fun w => D.Adj j w) Finset.univ) := by
          rw [← heq_i, ← heq_j]
  5. If there is an edge from i to j, we obtain a contradiction.

    Since i ≠ j, tournament completeness ensures exactly one edge between i and j. If i → j, then j ∈ N⁺(i). Since N⁺(i) = N⁺(j), this gives j ∈ N⁺(j), meaning j → j, which contradicts the irreflexivity of the tournament (hD.1).

    lines 37–43

    uses Finset.mem_filter, Finset.mem_univ

        have htourn := hD.2 i j hij
        by_cases hadj : D.Adj i j
        · have hj_in_i : j ∈ Finset.filter (fun w => D.Adj i w) Finset.univ := by
            rw [Finset.mem_filter]; exact ⟨Finset.mem_univ j, hadj⟩
          rw [hij_eq] at hj_in_i
          rw [Finset.mem_filter] at hj_in_i
          exact hD.1 j hj_in_i.2
  6. If instead there is an edge from j to i, we also obtain a contradiction.

    If there is no edge from i to j, the tournament condition forces an edge j → i. Then i ∈ N⁺(j), which via N⁺(i) = N⁺(j) implies i ∈ N⁺(i) and therefore i → i. This again contradicts irreflexivity, ruling out a common out-neighbour count of 2 and completing the proof.

    lines 44–52

    uses Finset.mem_filter, Finset.mem_univ

        · have h_ji : D.Adj j i := by
            by_contra h_not_ji
            apply hadj
            rwa [htourn]
          have hi_in_j : i ∈ Finset.filter (fun w => D.Adj j w) Finset.univ := by
            rw [Finset.mem_filter]; exact ⟨Finset.mem_univ i, h_ji⟩
          rw [← hij_eq] at hi_in_j
          rw [Finset.mem_filter] at hi_in_j
          exact hD.1 i hi_in_j.2
Finset.mem_filter
An element a belongs to the filtered sub-collection of s satisfying predicate p if and only if a ∈ s and p(a) holds.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then the cardinality of s is at most that of t.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets s and t, then s = t.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.

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

theorem regular_tournament_five_nearly_doubly_regular (D : Digraph (Fin 5))    [DecidableRel D.Adj] (hD : digraph_is_tournament D)    (hreg : ∀ v, digraph_out_count D v = 2) :    ∀ i j, i ≠ j → digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1 := by  intro i j hij  have hsub_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆      (Finset.filter (fun w => D.Adj i w) Finset.univ) := by    intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.1⟩  have hsub_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆      (Finset.filter (fun w => D.Adj j w) Finset.univ) := by    intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.2⟩  have hle : digraph_common_out_count D i j ≤ 2 := by    have h1 := Finset.card_le_card hsub_i    have h2 := hreg i    exact h1.trans_eq h2  have hcases : digraph_common_out_count D i j = 0 ∨                digraph_common_out_count D i j = 1 ∨                digraph_common_out_count D i j = 2 := by omega  rcases hcases with h0 | h1 | h2  · left; exact h0  · right; exact h1  · exfalso    have hcard_comm : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ).card = 2 := h2    have hcard_i : (Finset.filter (fun w => D.Adj i w) Finset.univ).card = 2 := hreg i    have hcard_j : (Finset.filter (fun w => D.Adj j w) Finset.univ).card = 2 := hreg j    have heq_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) =        (Finset.filter (fun w => D.Adj i w) Finset.univ) := by      apply Finset.eq_of_subset_of_card_le hsub_i      rw [hcard_comm, hcard_i]    have heq_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) =        (Finset.filter (fun w => D.Adj j w) Finset.univ) := by      apply Finset.eq_of_subset_of_card_le hsub_j      rw [hcard_comm, hcard_j]    have hij_eq : (Finset.filter (fun w => D.Adj i w) Finset.univ) =        (Finset.filter (fun w => D.Adj j w) Finset.univ) := by      rw [← heq_i, ← heq_j]    have htourn := hD.2 i j hij    by_cases hadj : D.Adj i j    · have hj_in_i : j ∈ Finset.filter (fun w => D.Adj i w) Finset.univ := by        rw [Finset.mem_filter]; exact ⟨Finset.mem_univ j, hadj⟩      rw [hij_eq] at hj_in_i      rw [Finset.mem_filter] at hj_in_i      exact hD.1 j hj_in_i.2    · have h_ji : D.Adj j i := by        by_contra h_not_ji        apply hadj        rwa [htourn]      have hi_in_j : i ∈ Finset.filter (fun w => D.Adj j w) Finset.univ := by        rw [Finset.mem_filter]; exact ⟨Finset.mem_univ i, h_ji⟩      rw [← hij_eq] at hi_in_j      rw [Finset.mem_filter] at hi_in_j      exact hD.1 i hi_in_j.2
See it in the graphDiscuss this resultChallenge it