AFTD Auto-Formalizing Theoretical Domains

arrows_grundy_three_witness_tree_structure

theoremverified

The explicit 21-vertex graph defined by 20 edges is a tree of maximum degree at most 3, all of whose piece threads have length at most 3.

Statement

theorem arrows_grundy_three_witness_tree_structure :
    ∃ (T : SimpleGraph (Fin 21)) (_ : DecidableRel T.Adj),
      T.IsTree ∧
      T.maxDegree ≤ 3 ∧
      (∀ (u v : Fin 21) (p : T.Walk u v), is_piece_thread T p → p.length ≤ 3) ∧
      T = SimpleGraph.fromRel (fun u v : Fin 21 => (u, v) ∈ [((1 : Fin 21), (0 : Fin 21)), (1, 2), (0, 8), (2, 3), (2, 6), (3, 4), (4, 5), (6, 7), (8, 9), (8, 14), (9, 10), (9, 13), (10, 11), (11, 12), (14, 15), (5, 16), (7, 17), (12, 18), (13, 19), (15, 20)])
Source
step towards subcubic_short_thread_arrows_grundy_three_achievable
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_piece_threadA thread of a piece of a tree T is a path of length at least 1 whose interior vertices have degree 2 and are not special, and whose…
  • is_tree_specialA vertex in a graph is special if it is not a leaf (degree not equal to 1) but is adjacent to a leaf (degree 1).
  • Arena.Reachable.transReachability is transitive.
  • supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

The proof, explained

The theorem proves the existence of a tree on 21 vertices with maximum degree at most 3 in which every piece thread has length at most 3, by constructing an explicit 20-edge graph. Connectedness is established by showing vertex 0 reaches every vertex by induction on vertex labels, which combined with the edge count shows the graph is a tree. The maximum degree bound is verified by finite computation. Finally, if any piece thread had length greater than 3, its interior would contain three consecutive vertices of degree 2 that are not adjacent to any leaf; exhaustive verification shows that no such vertex can have two distinct neighbors of this type, forcing two distinct path vertices to coincide, which contradicts the definition of a path.

  1. Adjacency in the witness graph is decidable.

    Given two vertices u, v ∈ Fin 21, adjacency is defined by checking whether the pair (u, v) or (v, u) belongs to an explicit finite list of 20 pairs with u ≠ v. Unfolding the definition allows Lean's typeclass resolution to synthesize the decidability instance.

    lines 11–13

      intro u v
      unfold arrows_grundy_three_witness_tree_structure_graph SimpleGraph.fromRel
      infer_instance
  2. The property of being a special tree vertex is decidable.

    A vertex is special if its degree is not 1 and it is adjacent to some degree-1 vertex. Because the vertex set Fin 21 is finite and adjacency is decidable, the existential search over neighbors and the degree computations are finite, so Lean synthesizes decidability.

    lines 17–19

      intro v
      unfold is_tree_special
      infer_instance
  3. Any walk vertex at an internal index i (1 ≤ i < p.length) belongs to the interior of the walk's vertex support.

    The interior of the walk's support is obtained by dropping the first and last elements. We show that the i-th vertex of p is at offset i - 1 in this list, by rewriting list operations and identifying the (i - 1)-th element of the dropped list with the i-th vertex of the walk.

    lines 26–32

    uses List.dropLast_drop_eq_drop_dropLast, List.mem_drop_iff_getElem, List.length_dropLast, SimpleGraph.Walk.length_support, List.getElem_dropLast, SimpleGraph.Walk.support_getElem_eq_getVert

      rw [List.dropLast_drop_eq_drop_dropLast, List.mem_drop_iff_getElem]
      refine ⟨i - 1, ?_, ?_⟩
      · rw [List.length_dropLast, SimpleGraph.Walk.length_support]; omega
      · rw [List.getElem_dropLast (by rw [List.length_dropLast, SimpleGraph.Walk.length_support]; omega)]
        rw [SimpleGraph.Walk.support_getElem_eq_getVert p (by rw [SimpleGraph.Walk.length_support]; omega)]
        have hidx : 1 + (i - 1) = i := by omega
        rw [hidx]
  4. In the witness graph, no degree-2 non-special vertex can have two distinct degree-2 non-special neighbors. automation

    Exhaustive finite evaluation (decide) over all triples of vertices (c, b, d) checks that if c has degree 2 and is non-special, and its neighbors b and d also have degree 2 and are non-special, then b = d.

    line 47

      decide
  5. Every vertex with positive index in the witness graph has an adjacent neighbor with strictly smaller index. automation

    Exhaustive finite evaluation (decide) over all 21 vertices verifies that every vertex u > 0 has a neighbor v < u in the edge list.

    line 53

      decide
  6. Vertex 0 can reach every vertex in the witness graph.

    By strengthening the goal to showing that 0 reaches every vertex u with u < n, we proceed by induction on n. The base case n = 0 is vacuously false. In the inductive step for n + 1, if u = 0, the trivial walk connects 0 to itself. If u > 0, by arrows_grundy_three_witness_tree_structure_parent there exists an adjacent neighbor v < u < n. By the induction hypothesis, there is a walk from 0 to v, which we extend by the edge (v, u) to reach u.

    lines 58–72

    uses Fin.ext, SimpleGraph.Walk.nil, Nat.pos_of_ne_zero, arrows_grundy_three_witness_tree_structure_parent, SimpleGraph.Walk.cons

      suffices h : ∀ n, ∀ u : Fin 21, u.val < n →
          arrows_grundy_three_witness_tree_structure_graph.Reachable 0 u from h 21 u u.isLt
      intro n
      induction n with
      | zero => intro u hu; omega
      | succ n ih =>
          intro u hu
          by_cases h0 : u.val = 0
          · have hu0 : u = 0 := Fin.ext h0
            subst hu0
            exact ⟨SimpleGraph.Walk.nil⟩
          · have hpos : 0 < u.val := Nat.pos_of_ne_zero h0
            obtain ⟨v, hvlt, hvu⟩ := arrows_grundy_three_witness_tree_structure_parent u hpos
            have hvltn : v.val < n := by omega
            exact (ih v hvltn).trans ⟨SimpleGraph.Walk.cons hvu SimpleGraph.Walk.nil⟩
  7. The witness graph is connected.

    Any two vertices u and v are connected by reversing the walk from 0 to u (yielding a walk from u to 0) and concatenating it with the walk from 0 to v, using arrows_grundy_three_witness_tree_structure_reachable_zero.

    lines 77–80

    uses SimpleGraph.Connected.mk, arrows_grundy_three_witness_tree_structure_reachable_zero

      refine SimpleGraph.Connected.mk ?_
      intro u v
      exact (arrows_grundy_three_witness_tree_structure_reachable_zero u).symm.trans
        (arrows_grundy_three_witness_tree_structure_reachable_zero v)
  8. The witness graph has 20 edges, so |E| + 1 = |V|. automation

    We rewrite the cardinality of the edge set to the cardinality of the finite edge set, which is then computed exhaustively by decide to be 20, satisfying 20 + 1 = 21.

    lines 85–86

    uses Nat.card_eq_fintype_card, SimpleGraph.edgeFinset_card

      rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card]
      decide
  9. The witness graph is a tree.

    By SimpleGraph.isTree_iff_connected_and_card, a finite graph is a tree if and only if it is connected and has |E| + 1 = |V|. Both conditions were established in arrows_grundy_three_witness_tree_structure_connected and arrows_grundy_three_witness_tree_structure_card.

    lines 91–93

    uses SimpleGraph.isTree_iff_connected_and_card, arrows_grundy_three_witness_tree_structure_connected, arrows_grundy_three_witness_tree_structure_card

      rw [SimpleGraph.isTree_iff_connected_and_card]
      exact ⟨arrows_grundy_three_witness_tree_structure_connected,
        arrows_grundy_three_witness_tree_structure_card⟩
  10. The maximum degree of the witness graph is at most 3. automation

    Lean's computational kernel (decide) calculates the degree of all 21 vertices and confirms that each is at most 3.

    line 98

      decide
  11. If a piece thread has length at least 4, its first three internal vertices p(1), p(2), p(3) all have degree 2 and are non-special.

    Assume for contradiction that a piece thread p has length > 3, so its length is at least 4. By lemma arrows_grundy_three_witness_tree_structure_getVert_mem_interior, the vertices p(1), p(2), and p(3) all lie in the interior of p. By the definition of a piece thread, every interior vertex has degree 2 and is not special.

    lines 105–116

    uses arrows_grundy_three_witness_tree_structure_getVert_mem_interior

      by_contra h
      have hidx1 : 1 < p.length := by omega
      have hidx2 : 2 < p.length := by omega
      have hidx3 : 3 < p.length := by omega
      have hlen1 : 1 ≤ p.length := by omega
      have hlen3 : 3 ≤ p.length := by omega
      obtain ⟨hd1, hs1⟩ := hp.2.2.2.2 (p.getVert 1)
        (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx1)
      obtain ⟨hd2, hs2⟩ := hp.2.2.2.2 (p.getVert 2)
        (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx2)
      obtain ⟨hd3, hs3⟩ := hp.2.2.2.2 (p.getVert 3)
        (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx3)
  12. The first and third internal vertices of the piece thread are equal: p(1) = p(3).

    Since p(1) is adjacent to p(2) and p(2) is adjacent to p(3), both p(1) and p(3) are degree-2 non-special neighbors of the degree-2 non-special vertex p(2). By lemma arrows_grundy_three_witness_tree_structure_center, this vertex cannot have two distinct such neighbors, so p(1) = p(3).

    lines 117–123

    uses arrows_grundy_three_witness_tree_structure_center

      have hadj12 : arrows_grundy_three_witness_tree_structure_graph.Adj (p.getVert 1) (p.getVert 2) :=
        p.adj_getVert_succ hidx1
      have hadj23 : arrows_grundy_three_witness_tree_structure_graph.Adj (p.getVert 2) (p.getVert 3) :=
        p.adj_getVert_succ hidx2
      have heq : p.getVert 1 = p.getVert 3 :=
        arrows_grundy_three_witness_tree_structure_center (p.getVert 2) (p.getVert 1) (p.getVert 3)
          hadj12.symm hadj23 hd2 hs2 hd1 hs1 hd3 hs3
  13. Every piece thread in the witness graph has length at most 3.

    Because p is a path, its vertex assignment is injective on indices. In particular, since 1 ≠ 3, we must have p(1) ≠ p(3). This directly contradicts the equality p(1) = p(3) obtained in the previous step.

    lines 124–128

      have hne : p.getVert 1 ≠ p.getVert 3 := by
        intro hc
        have h13 := hp.1.getVert_injOn (by simp [hlen1]) (by simp [hlen3]) hc
        omega
      exact hne heq
  14. There exists a 21-vertex tree with maximum degree at most 3 and all piece threads of length at most 3.

    We instantiate the existential statement with the explicit 21-vertex graph and its adjacency decider, and combine the four proven properties: it is a tree, its maximum degree is at most 3, all piece threads have length at most 3, and its edge relation matches the given 20 edges by definition.

    lines 137–142

    uses arrows_grundy_three_witness_tree_structure_isTree, arrows_grundy_three_witness_tree_structure_maxDegree, arrows_grundy_three_witness_tree_structure_thread

      refine ⟨arrows_grundy_three_witness_tree_structure_graph,
        arrows_grundy_three_witness_tree_structure_decAdj, ?_, ?_, ?_, ?_⟩
      · exact arrows_grundy_three_witness_tree_structure_isTree
      · exact arrows_grundy_three_witness_tree_structure_maxDegree
      · exact arrows_grundy_three_witness_tree_structure_thread
      · rfl
List.dropLast_drop_eq_drop_dropLast
Dropping the last element of a list after dropping its first n elements is equal to dropping the first n elements after dropping the last element.
List.mem_drop_iff_getElem
An element belongs to the suffix of a list starting at index i if and only if it equals the element at index i + j for some valid offset j.
List.length_dropLast
Dropping the last element of a list reduces its length by 1.
SimpleGraph.Walk.length_support
The vertex support list of a walk has length equal to the length of the walk plus 1.
List.getElem_dropLast
For any valid index i in a list without its last element, the i-th element is the same as in the original list.
SimpleGraph.Walk.support_getElem_eq_getVert
The n-th element of a walk's vertex support is the n-th vertex of the walk.
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
SimpleGraph.Walk.nil
The trivial walk of length 0 starting and ending at the same vertex.
Nat.pos_of_ne_zero
If a natural number is not zero, then it is strictly positive.
arrows_grundy_three_witness_tree_structure_parent
Every vertex with positive index in the witness graph has an adjacent neighbor of strictly smaller index.
SimpleGraph.Walk.cons
Prepending an adjacent edge to a walk produces a new walk extended by one step.
SimpleGraph.Connected.mk
A graph is connected if it is nonempty and every pair of vertices can reach each other by a walk.
arrows_grundy_three_witness_tree_structure_reachable_zero
In the witness graph, vertex 0 can reach every vertex via a walk.
Nat.card_eq_fintype_card
The cardinality Nat.card of a finite type equals the number of elements given by Fintype.card.
SimpleGraph.edgeFinset_card
The size of a graph's finite edge set edgeFinset equals the cardinality of its edge set.
SimpleGraph.isTree_iff_connected_and_card
A finite graph is a tree if and only if it is connected and its number of edges plus 1 equals its number of vertices.
arrows_grundy_three_witness_tree_structure_connected
The witness graph is connected.
arrows_grundy_three_witness_tree_structure_card
The witness graph has 20 edges and 21 vertices, so |E| + 1 = |V|.
arrows_grundy_three_witness_tree_structure_getVert_mem_interior
For any walk p and index 1 ≤ i < p.length, the i-th vertex of p belongs to the interior vertex list of p.
arrows_grundy_three_witness_tree_structure_center
In the witness graph, a degree-2 non-special vertex cannot have two distinct degree-2 non-special neighbors.
arrows_grundy_three_witness_tree_structure_isTree
The witness graph is a tree.
arrows_grundy_three_witness_tree_structure_maxDegree
The maximum degree of the witness graph is at most 3.
arrows_grundy_three_witness_tree_structure_thread
Every piece thread in the witness graph has length at most 3.

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

/-- The edge list of the 21-vertex witness graph. -/def arrows_grundy_three_witness_tree_structure_rlist : List (Fin 21 × Fin 21) :=  [((1 : Fin 21), (0 : Fin 21)), (1, 2), (0, 8), (2, 3), (2, 6), (3, 4), (4, 5), (6, 7), (8, 9), (8, 14), (9, 10), (9, 13), (10, 11), (11, 12), (14, 15), (5, 16), (7, 17), (12, 18), (13, 19), (15, 20)]/-- The 21-vertex witness graph. -/def arrows_grundy_three_witness_tree_structure_graph : SimpleGraph (Fin 21) :=  SimpleGraph.fromRel (fun u v : Fin 21 => (u, v) ∈ arrows_grundy_three_witness_tree_structure_rlist)instance arrows_grundy_three_witness_tree_structure_decAdj :    DecidableRel arrows_grundy_three_witness_tree_structure_graph.Adj := by  intro u v  unfold arrows_grundy_three_witness_tree_structure_graph SimpleGraph.fromRel  infer_instanceinstance arrows_grundy_three_witness_tree_structure_decSpecial :    DecidablePred (is_tree_special arrows_grundy_three_witness_tree_structure_graph) := by  intro v  unfold is_tree_special  infer_instance/-- Vertices at internal walk positions lie in the interior vertex list of the thread. -/lemma arrows_grundy_three_witness_tree_structure_getVert_mem_interior    {u v : Fin 21} (p : arrows_grundy_three_witness_tree_structure_graph.Walk u v) {i : ℕ}    (h1 : 1 ≤ i) (h2 : i < p.length) :    p.getVert i ∈ (p.support.drop 1).dropLast := by  rw [List.dropLast_drop_eq_drop_dropLast, List.mem_drop_iff_getElem]  refine ⟨i - 1, ?_, ?_⟩  · rw [List.length_dropLast, SimpleGraph.Walk.length_support]; omega  · rw [List.getElem_dropLast (by rw [List.length_dropLast, SimpleGraph.Walk.length_support]; omega)]    rw [SimpleGraph.Walk.support_getElem_eq_getVert p (by rw [SimpleGraph.Walk.length_support]; omega)]    have hidx : 1 + (i - 1) = i := by omega    rw [hidx]/-- Locally in the witness graph, a degree-2 non-special vertex has its two neighboursuniquely determined up to symmetry: no two distinct neighbours of it are both degree-2 andnon-special. -/lemma arrows_grundy_three_witness_tree_structure_center :    ∀ (c b d : Fin 21),      arrows_grundy_three_witness_tree_structure_graph.Adj c b →      arrows_grundy_three_witness_tree_structure_graph.Adj c d →      arrows_grundy_three_witness_tree_structure_graph.degree c = 2 →      ¬ is_tree_special arrows_grundy_three_witness_tree_structure_graph c →      arrows_grundy_three_witness_tree_structure_graph.degree b = 2 →      ¬ is_tree_special arrows_grundy_three_witness_tree_structure_graph b →      arrows_grundy_three_witness_tree_structure_graph.degree d = 2 →      ¬ is_tree_special arrows_grundy_three_witness_tree_structure_graph d → b = d := by  decide/-- Every vertex of the witness graph with positive index has a neighbour of smaller index. -/lemma arrows_grundy_three_witness_tree_structure_parent :    ∀ u : Fin 21, 0 < u.val →      ∃ v : Fin 21, v.val < u.val ∧ arrows_grundy_three_witness_tree_structure_graph.Adj v u := by  decide/-- Vertex `0` reaches every vertex of the witness graph. -/lemma arrows_grundy_three_witness_tree_structure_reachable_zero (u : Fin 21) :    arrows_grundy_three_witness_tree_structure_graph.Reachable 0 u := by  suffices h : ∀ n, ∀ u : Fin 21, u.val < n →      arrows_grundy_three_witness_tree_structure_graph.Reachable 0 u from h 21 u u.isLt  intro n  induction n with  | zero => intro u hu; omega  | succ n ih =>      intro u hu      by_cases h0 : u.val = 0      · have hu0 : u = 0 := Fin.ext h0        subst hu0        exact ⟨SimpleGraph.Walk.nil⟩      · have hpos : 0 < u.val := Nat.pos_of_ne_zero h0        obtain ⟨v, hvlt, hvu⟩ := arrows_grundy_three_witness_tree_structure_parent u hpos        have hvltn : v.val < n := by omega        exact (ih v hvltn).trans ⟨SimpleGraph.Walk.cons hvu SimpleGraph.Walk.nil⟩/-- The witness graph is connected. -/lemma arrows_grundy_three_witness_tree_structure_connected :    arrows_grundy_three_witness_tree_structure_graph.Connected := by  refine SimpleGraph.Connected.mk ?_  intro u v  exact (arrows_grundy_three_witness_tree_structure_reachable_zero u).symm.trans    (arrows_grundy_three_witness_tree_structure_reachable_zero v)/-- The witness graph has 20 edges, one fewer than its number of vertices. -/lemma arrows_grundy_three_witness_tree_structure_card :    Nat.card arrows_grundy_three_witness_tree_structure_graph.edgeSet + 1 = Nat.card (Fin 21) := by  rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card]  decide/-- The witness graph is a tree. -/lemma arrows_grundy_three_witness_tree_structure_isTree :    arrows_grundy_three_witness_tree_structure_graph.IsTree := by  rw [SimpleGraph.isTree_iff_connected_and_card]  exact ⟨arrows_grundy_three_witness_tree_structure_connected,    arrows_grundy_three_witness_tree_structure_card⟩/-- The witness graph has maximum degree at most 3. -/lemma arrows_grundy_three_witness_tree_structure_maxDegree :    arrows_grundy_three_witness_tree_structure_graph.maxDegree ≤ 3 := by  decide/-- Every piece thread of the witness graph has length at most 3. -/lemma arrows_grundy_three_witness_tree_structure_thread (u v : Fin 21)    (p : arrows_grundy_three_witness_tree_structure_graph.Walk u v)    (hp : is_piece_thread arrows_grundy_three_witness_tree_structure_graph p) :    p.length ≤ 3 := by  by_contra h  have hidx1 : 1 < p.length := by omega  have hidx2 : 2 < p.length := by omega  have hidx3 : 3 < p.length := by omega  have hlen1 : 1 ≤ p.length := by omega  have hlen3 : 3 ≤ p.length := by omega  obtain ⟨hd1, hs1⟩ := hp.2.2.2.2 (p.getVert 1)    (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx1)  obtain ⟨hd2, hs2⟩ := hp.2.2.2.2 (p.getVert 2)    (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx2)  obtain ⟨hd3, hs3⟩ := hp.2.2.2.2 (p.getVert 3)    (arrows_grundy_three_witness_tree_structure_getVert_mem_interior p (by norm_num) hidx3)  have hadj12 : arrows_grundy_three_witness_tree_structure_graph.Adj (p.getVert 1) (p.getVert 2) :=    p.adj_getVert_succ hidx1  have hadj23 : arrows_grundy_three_witness_tree_structure_graph.Adj (p.getVert 2) (p.getVert 3) :=    p.adj_getVert_succ hidx2  have heq : p.getVert 1 = p.getVert 3 :=    arrows_grundy_three_witness_tree_structure_center (p.getVert 2) (p.getVert 1) (p.getVert 3)      hadj12.symm hadj23 hd2 hs2 hd1 hs1 hd3 hs3  have hne : p.getVert 1 ≠ p.getVert 3 := by    intro hc    have h13 := hp.1.getVert_injOn (by simp [hlen1]) (by simp [hlen3]) hc    omega  exact hne heq/-- The explicit 21-vertex graph defined by 20 edges is a tree of maximum degree at most 3, all of whose piece threads have length at most 3. -/theorem arrows_grundy_three_witness_tree_structure :    ∃ (T : SimpleGraph (Fin 21)) (_ : DecidableRel T.Adj),      T.IsTree ∧      T.maxDegree ≤ 3 ∧      (∀ (u v : Fin 21) (p : T.Walk u v), is_piece_thread T p → p.length ≤ 3) ∧      T = SimpleGraph.fromRel (fun u v : Fin 21 => (u, v) ∈ [((1 : Fin 21), (0 : Fin 21)), (1, 2), (0, 8), (2, 3), (2, 6), (3, 4), (4, 5), (6, 7), (8, 9), (8, 14), (9, 10), (9, 13), (10, 11), (11, 12), (14, 15), (5, 16), (7, 17), (12, 18), (13, 19), (15, 20)]) := by  refine ⟨arrows_grundy_three_witness_tree_structure_graph,    arrows_grundy_three_witness_tree_structure_decAdj, ?_, ?_, ?_, ?_⟩  · exact arrows_grundy_three_witness_tree_structure_isTree  · exact arrows_grundy_three_witness_tree_structure_maxDegree  · exact arrows_grundy_three_witness_tree_structure_thread  · rfl
See it in the graphDiscuss this resultChallenge it