AFTD Auto-Formalizing Theoretical Domains

op223_weighted_support_graph_is_tree

theoremverified

The support graph of the rational weighted-shift candidate is a tree.

Statement

theorem op223_weighted_support_graph_is_tree : op223_weighted_support_graph.IsTree
Source
The finite weighted-shift counterexample candidate.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem proves that the support graph on 13 vertices is a tree using the characterization that a finite simple graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices. Connectedness is established by showing that every vertex is reachable from vertex 0 along paths formed by the graph's 12 defined edges. A helper lemma identifies the edge set with the explicit 12-element set by checking that no edge is a self-loop. Finally, arithmetic computation verifies that the 12 edges and 13 vertices satisfy |E| + 1 = |V|.

  1. The edge set of the support graph consists exactly of the 12 specified vertex pairs.

    By definition, a simple graph constructed from a set of pairs has as its edges all pairs in that set that are not self-loops (diagonal elements). Since an exhaustive check via decision procedure shows that none of the 12 specified pairs are diagonal, the edge set coincides with the 12-element set.

    lines 7–17

    uses SimpleGraph.edgeSet_fromEdgeSet, Set.mem_sdiff, Sym2.mem_diagSet, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, And.left

      classical
      rw [op223_weighted_support_graph, SimpleGraph.edgeSet_fromEdgeSet]
      ext e
      simp only [Set.mem_sdiff, Sym2.mem_diagSet, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]
      constructor
      · exact And.left
      · intro he
        refine ⟨he, ?_⟩
        have h : ∀ x ∈ ({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))), ¬ x.IsDiag := by decide
        apply h e
        simpa only [Finset.mem_insert, Finset.mem_singleton] using he
  2. Each of the 12 specified vertex pairs forms an edge in the support graph.

    For each pair (0,1), (1,2), (2,3), (3,4), (4,5), (0,6), (0,7), (7,8), (8,9), (9,10), (10,11), and (11,12), adjacency holds by simplifying against the graph's definition and the condition that the two endpoints are distinct.

    lines 20–32

    uses SimpleGraph.fromEdgeSet_adj, Sym2.eq

      classical
      have e01 : op223_weighted_support_graph.Adj 0 1 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e12 : op223_weighted_support_graph.Adj 1 2 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e23 : op223_weighted_support_graph.Adj 2 3 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e34 : op223_weighted_support_graph.Adj 3 4 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e45 : op223_weighted_support_graph.Adj 4 5 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e06 : op223_weighted_support_graph.Adj 0 6 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e07 : op223_weighted_support_graph.Adj 0 7 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e78 : op223_weighted_support_graph.Adj 7 8 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e89 : op223_weighted_support_graph.Adj 8 9 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e910 : op223_weighted_support_graph.Adj 9 10 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e1011 : op223_weighted_support_graph.Adj 10 11 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e1112 : op223_weighted_support_graph.Adj 11 12 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
  3. To prove that the graph is a tree, it suffices to show that it is connected and that |E| + 1 = |V|.

    By the standard characterization of finite trees, a simple graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices. Applying this characterization splits the goal into two subgoals: connectedness and the cardinality equality.

    lines 33–34

    uses SimpleGraph.isTree_iff_connected_and_card.mpr

      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
  4. The support graph is connected because every vertex is reachable from vertex 0.

    A graph is connected if and only if there is a vertex from which all vertices are reachable. Choosing 0 as the root, an exhaustive case analysis on all 13 vertices of Fin 13 establishes reachability: 0 is reachable from itself by reflexivity; 1 through 5 are reachable along the path 0–1–2–3–4–5; 6 is an immediate neighbor of 0; and 7 through 12 are reachable along the path 0–7–8–9–10–11–12.

    lines 35–51

    uses SimpleGraph.connected_iff_exists_forall_reachable, Reachable.rfl

      · rw [SimpleGraph.connected_iff_exists_forall_reachable]
        refine ⟨0, ?_⟩
        intro x
        fin_cases x
        · exact Reachable.rfl
        · exact e01.reachable
        · exact e01.reachable.trans e12.reachable
        · exact (e01.reachable.trans e12.reachable).trans e23.reachable
        · exact ((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable
        · exact (((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable).trans e45.reachable
        · exact e06.reachable
        · exact e07.reachable
        · exact e07.reachable.trans e78.reachable
        · exact (e07.reachable.trans e78.reachable).trans e89.reachable
        · exact ((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable
        · exact (((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable
        · exact ((((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable).trans e1112.reachable
  5. The number of edges plus one equals the number of vertices (12 + 1 = 13), completing the proof that the graph is a tree. automation

    Rewriting with the helper lemma op223_weighted_support_edges converts the edge set cardinality into the size of the explicit 12-element set. Normalization and computation confirm that the edge set has cardinality 12 and Fin 13 has cardinality 13, satisfying 12 + 1 = 13.

    lines 52–53

    uses Nat.card_coe_set_eq, op223_weighted_support_edges, Set.ncard_coe_finset, Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card

      · rw [Nat.card_coe_set_eq, op223_weighted_support_edges, Set.ncard_coe_finset]
        norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
And.left
From a conjunction a ∧ b, one deduces the left conjunct a.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_insert_eq_ite
Inserting an element into a finite set increases its cardinality by 1 if the element was not already present, and leaves it unchanged otherwise.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton finite set {a} if and only if it equals a.
Nat.card_eq_fintype_card
The cardinal number of a finite type equals the cardinality given by its Fintype instance.
Nat.card_coe_set_eq
The cardinal number of a coerced set equals its finite cardinality (ncard).
op223_weighted_support_edges
The edge set of the candidate support graph consists precisely of the 12 specified unordered pairs.
Reachable.rfl
Every vertex in a graph is reachable from itself.
Set.ncard_coe_finset
The set cardinality (ncard) of a coerced finite set equals its finite set cardinality (card).
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
SimpleGraph.connected_iff_exists_forall_reachable
A graph is connected if and only if there exists a vertex that can reach every vertex.
SimpleGraph.edgeSet_fromEdgeSet
The edge set of a simple graph generated from a set of pairs s is s minus all diagonal pairs (self-loops).
SimpleGraph.fromEdgeSet_adj
Two vertices v and w are adjacent in SimpleGraph.fromEdgeSet s if and only if the pair s(v, w) is in s and v ≠ w.
SimpleGraph.isTree_iff_connected_and_card.mpr
A simple graph on a finite vertex set is a tree if and only if it is connected and |E| + 1 = |V|.
Sym2.eq
Two unordered pairs s(a, b) and s(c, d) are equal if and only if (a = c ∧ b = d) or (a = d ∧ b = c).
Sym2.mem_diagSet
An unordered pair belongs to the diagonal set if and only if both endpoints are equal.

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 SimpleGraphopen scoped Classicalset_option maxHeartbeats 1000000set_option maxRecDepth 10000lemma op223_weighted_support_edges : op223_weighted_support_graph.edgeSet =    (({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))) : Set (Sym2 (Fin 13))) := by  classical  rw [op223_weighted_support_graph, SimpleGraph.edgeSet_fromEdgeSet]  ext e  simp only [Set.mem_sdiff, Sym2.mem_diagSet, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]  constructor  · exact And.left  · intro he    refine ⟨he, ?_⟩    have h : ∀ x ∈ ({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))), ¬ x.IsDiag := by decide    apply h e    simpa only [Finset.mem_insert, Finset.mem_singleton] using hetheorem op223_weighted_support_graph_is_tree : op223_weighted_support_graph.IsTree := by  classical  have e01 : op223_weighted_support_graph.Adj 0 1 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e12 : op223_weighted_support_graph.Adj 1 2 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e23 : op223_weighted_support_graph.Adj 2 3 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e34 : op223_weighted_support_graph.Adj 3 4 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e45 : op223_weighted_support_graph.Adj 4 5 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e06 : op223_weighted_support_graph.Adj 0 6 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e07 : op223_weighted_support_graph.Adj 0 7 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e78 : op223_weighted_support_graph.Adj 7 8 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e89 : op223_weighted_support_graph.Adj 8 9 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e910 : op223_weighted_support_graph.Adj 9 10 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e1011 : op223_weighted_support_graph.Adj 10 11 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e1112 : op223_weighted_support_graph.Adj 11 12 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  apply SimpleGraph.isTree_iff_connected_and_card.mpr  constructor  · rw [SimpleGraph.connected_iff_exists_forall_reachable]    refine ⟨0, ?_⟩    intro x    fin_cases x    · exact Reachable.rfl    · exact e01.reachable    · exact e01.reachable.trans e12.reachable    · exact (e01.reachable.trans e12.reachable).trans e23.reachable    · exact ((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable    · exact (((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable).trans e45.reachable    · exact e06.reachable    · exact e07.reachable    · exact e07.reachable.trans e78.reachable    · exact (e07.reachable.trans e78.reachable).trans e89.reachable    · exact ((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable    · exact (((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable    · exact ((((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable).trans e1112.reachable  · rw [Nat.card_coe_set_eq, op223_weighted_support_edges, Set.ncard_coe_finset]    norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
See it in the graphDiscuss this resultChallenge it