arrows_grundy_three_witness_tree_structure
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.
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.
intro u v unfold arrows_grundy_three_witness_tree_structure_graph SimpleGraph.fromRel infer_instance
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.
intro v unfold is_tree_special infer_instance
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.
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_getVertrw [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]
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.
decideEvery 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.
decideVertex 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.
uses
Fin.ext,SimpleGraph.Walk.nil,Nat.pos_of_ne_zero,arrows_grundy_three_witness_tree_structure_parent,SimpleGraph.Walk.conssuffices 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.
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.
uses
SimpleGraph.Connected.mk,arrows_grundy_three_witness_tree_structure_reachable_zerorefine 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, 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.
uses
Nat.card_eq_fintype_card,SimpleGraph.edgeFinset_cardrw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card] decide
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.
uses
SimpleGraph.isTree_iff_connected_and_card,arrows_grundy_three_witness_tree_structure_connected,arrows_grundy_three_witness_tree_structure_cardrw [SimpleGraph.isTree_iff_connected_and_card] exact ⟨arrows_grundy_three_witness_tree_structure_connected, arrows_grundy_three_witness_tree_structure_card⟩
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.
decideIf 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.
uses
arrows_grundy_three_witness_tree_structure_getVert_mem_interiorby_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)
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).
uses
arrows_grundy_three_witness_tree_structure_centerhave 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
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.
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
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.
uses
arrows_grundy_three_witness_tree_structure_isTree,arrows_grundy_three_witness_tree_structure_maxDegree,arrows_grundy_three_witness_tree_structure_threadrefine ⟨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.
- Several local combinatorial properties of the explicit 21-vertex graph (parent existence, edge and degree counts, and the uniqueness of degree-2 non-special neighbors) are verified by Lean's computational kernel via `decide` rather than pen-and-paper deductions.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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