AFTD Auto-Formalizing Theoretical Domains

tournament_is_king_of_max_outdegree

theoremverifiedformalization

In every tournament on n vertices, every vertex of maximum outdegree is a king: every other vertex is reachable from it by a directed path of length at most two.

Statement

open Classical in
theorem tournament_is_king_of_max_outdegree {n : ℕ} (T : Digraph (Fin n))
    (hT : digraph_is_tournament T) (v : Fin n)
    (hmax : ∀ u : Fin n, digraph_out_count T u ≤ digraph_out_count T v) :
    ∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u
Formalizes
arXiv:2610.40521 Equation 2
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Used by 1

Read back from the Lean

For every natural number n, directed graph T with vertices Fin n, and vertex v : Fin n, if T is a tournament (meaning T has no self-loops, and for all distinct vertices x and y, there is an edge from x to y if and only if there is no edge from y to x), and if v has maximum out-degree in T (for every vertex u : Fin n, the number of vertices w such that T.Adj u w is at most the number of vertices w such that T.Adj v w), then for every vertex u : Fin n distinct from v, either there is a directed edge from v to u, or there exists an intermediate vertex w : Fin n such that there are directed edges from v to w and from w to u (i.e., v is a king).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

We argue by contradiction: suppose a vertex v of maximum outdegree cannot reach some vertex u in at most two steps. Then u must dominate v, and every out-neighbor of v must also be dominated by u (otherwise v could reach u in two steps via that out-neighbor). Consequently, the out-neighborhood of u contains v along with the entire out-neighborhood of v. Since tournaments have no self-loops, this forces u to have strictly greater outdegree than v, contradicting the maximality of v's outdegree.

  1. Assume for contradiction that some vertex u ≠ v is not reachable from v by a directed path of length at most two, and unpack the tournament hypotheses.

    We fix a vertex u ≠ v and assume for contradiction that v cannot reach u in one step (¬T.Adj v u) and cannot reach u in two steps via any intermediate vertex w (if T.Adj v w then ¬T.Adj w u). We also unpack the tournament hypothesis into irreflexivity (no vertex has a self-loop) and the tournament condition (for any two distinct vertices, exactly one directed edge connects them).

    lines 7–11

      intro u huv
      by_contra h
      push Not at h
      obtain ⟨hv_ne_u, hcover⟩ := h
      obtain ⟨hirr, htour⟩ := hT
  2. There is a directed arc from u to v.

    Since u ≠ v and there is no arc from v to u, the tournament condition requires that the directed arc must run from u to v (T.Adj u v).

    line 12

      have huv_arc : T.Adj u v := (htour u v huv).mpr hv_ne_u
  3. Every out-neighbor of v is also an out-neighbor of u.

    Let x be an out-neighbor of v (T.Adj v x). First, x cannot equal u because that would mean T.Adj v u, which we assumed is false. Second, since T.Adj v x and v cannot reach u in two steps, there cannot be an arc from x to u (¬T.Adj x u). By the tournament condition applied to distinct vertices u and x, ¬T.Adj x u implies an arc from u to x (T.Adj u x).

    lines 13–17

      have hcovx : ∀ x, T.Adj v x → T.Adj u x := by
        intro x hvx
        have hxu : x ≠ u := by
          intro hx; subst hx; exact hv_ne_u hvx
        exact (htour u x hxu.symm).mpr (hcover x hvx)
  4. The set {v} ∪ N⁺(v) is a subset of N⁺(u).

    For any x in {v} ∪ N⁺(v), either x = v or x ∈ N⁺(v). If x = v, we have T.Adj u v from the earlier step. If x ∈ N⁺(v), then T.Adj u x because every out-neighbor of v is an out-neighbor of u. Thus in both cases x is an out-neighbor of u.

    lines 18–24

    uses Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and

      have hsub : (insert v (Finset.univ.filter (fun w => T.Adj v w))) ⊆
          (Finset.univ.filter (fun w => T.Adj u w)) := by
        intro x hx
        simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢
        rcases hx with rfl | hvx
        · exact huv_arc
        · exact hcovx x hvx
  5. The vertex v is not in its own out-neighborhood.

    By the irreflexivity of the tournament, there is no self-loop T.Adj v v, so v does not belong to the set of out-neighbors of v.

    lines 25–26

      have hnotmem : v ∉ Finset.univ.filter (fun w => T.Adj v w) := by
        simp [hirr v]
  6. |N⁺(v)| + 1 ≤ |N⁺(u)|.

    Because {v} ∪ N⁺(v) ⊆ N⁺(u), the subset has cardinality at most |N⁺(u)| by Finset.card_le_card. Since v ∉ N⁺(v), inserting v increases the cardinality of N⁺(v) by 1 via Finset.card_insert_of_notMem, yielding |N⁺(v)| + 1 ≤ |N⁺(u)|.

    lines 27–31

    uses Finset.card_le_card, Finset.card_insert_of_notMem

      have hcard : (Finset.univ.filter (fun w => T.Adj v w)).card + 1 ≤
          (Finset.univ.filter (fun w => T.Adj u w)).card := by
        have := Finset.card_le_card hsub
        rw [Finset.card_insert_of_notMem hnotmem] at this
        exact this
  7. A contradiction is reached against the maximality of the outdegree of v.

    By the maximality assumption on v, the outdegree of u is at most that of v (|N⁺(u)| ≤ |N⁺(v)|). Unfolding the definition of outdegree (digraph_out_count) produces an immediate linear integer arithmetic contradiction with |N⁺(v)| + 1 ≤ |N⁺(u)|, which omega closes.

    lines 32–34

    uses digraph_out_count

      have hle := hmax u
      simp only [digraph_out_count] at hle
      omega
Finset.mem_insert
An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
The conjunction True ∧ p is equivalent to p.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_insert_of_notMem
Inserting an element a into a finset s not containing a yields a set of cardinality |s| + 1.
digraph_out_count
The outdegree of a vertex v in a directed graph is defined as the cardinality of its out-neighborhood {w | T.Adj v w}.

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

open Classical in/-- In any tournament on Fin n, every vertex of maximum outdegree is a king. -/theorem tournament_is_king_of_max_outdegree {n : ℕ} (T : Digraph (Fin n))    (hT : digraph_is_tournament T) (v : Fin n)    (hmax : ∀ u : Fin n, digraph_out_count T u ≤ digraph_out_count T v) :    ∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u := by  intro u huv  by_contra h  push Not at h  obtain ⟨hv_ne_u, hcover⟩ := h  obtain ⟨hirr, htour⟩ := hT  have huv_arc : T.Adj u v := (htour u v huv).mpr hv_ne_u  have hcovx : ∀ x, T.Adj v x → T.Adj u x := by    intro x hvx    have hxu : x ≠ u := by      intro hx; subst hx; exact hv_ne_u hvx    exact (htour u x hxu.symm).mpr (hcover x hvx)  have hsub : (insert v (Finset.univ.filter (fun w => T.Adj v w))) ⊆      (Finset.univ.filter (fun w => T.Adj u w)) := by    intro x hx    simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢    rcases hx with rfl | hvx    · exact huv_arc    · exact hcovx x hvx  have hnotmem : v ∉ Finset.univ.filter (fun w => T.Adj v w) := by    simp [hirr v]  have hcard : (Finset.univ.filter (fun w => T.Adj v w)).card + 1 ≤      (Finset.univ.filter (fun w => T.Adj u w)).card := by    have := Finset.card_le_card hsub    rw [Finset.card_insert_of_notMem hnotmem] at this    exact this  have hle := hmax u  simp only [digraph_out_count] at hle  omega
See it in the graphDiscuss this resultChallenge it