AFTD Auto-Formalizing Theoretical Domains

op223_weighted_eleven_graph_is_tree

theoremverified

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

Statement

theorem op223_weighted_eleven_graph_is_tree : op223_weighted_eleven_graph.IsTree
Source
The finite rational weighted-shift candidate.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof establishes that the 11-vertex support graph is a tree by showing it is connected and has 10 edges, satisfying the characterization |E| + 1 = |V|. Connectedness is proven by showing vertex 0 can reach every other vertex along explicit paths, and the edge count is computed directly from the explicit set of 10 generating edges.

  1. The edge set of op223_weighted_eleven_graph is precisely the 10-element set of candidate edges.

    By definition, SimpleGraph.fromEdgeSet creates a graph whose edges are the given pairs without self-loops. Because none of the 10 edges are loops (verified by decide), the diagonal set has empty intersection with the edges, so the edge set is exactly the given 10 edges.

    lines 7–17

    uses op223_weighted_eleven_graph, 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_eleven_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(0,10)} : Finset (Sym2 (Fin 11))), ¬ x.IsDiag := by decide
        apply h e
        simpa only [Finset.mem_insert, Finset.mem_singleton] using he
  2. The 10 candidate edges are each adjacent in the graph.

    Each of the 10 pairs (0,1), (1,2), (2,3), (3,4), (4,5), (0,6), (0,7), (7,8), (8,9), and (0,10) is verified to be an edge of op223_weighted_eleven_graph by unfolding the graph definition and simplifying using the adjacency rule for graphs from edge sets and pair symmetry.

    lines 20–30

    uses op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq

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

    We apply SimpleGraph.isTree_iff_connected_and_card.mpr, which states that a finite graph with |E| + 1 = |V| is a tree if and only if it is connected, and split the goal into connectedness and the cardinality equality.

    lines 31–32

    uses SimpleGraph.isTree_iff_connected_and_card.mpr

      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
  4. Connectedness reduces to showing every vertex is reachable from vertex 0.

    A graph is connected if some vertex can reach all vertices. We choose vertex 0 as this root and consider an arbitrary vertex x.

    lines 33–35

    uses SimpleGraph.connected_iff_exists_forall_reachable

      · rw [SimpleGraph.connected_iff_exists_forall_reachable]
        refine ⟨0, ?_⟩
        intro x
  5. Vertex 0 can reach every vertex in Fin 11.

    By case exhaustion on x in Fin 11, vertex 0 reaches 0 reflexively; vertices 1, 6, 7, 10 directly via an edge; vertices 2, 3, 4, 5 along the path 0-1-2-3-4-5; and vertices 8, 9 along the path 0-7-8-9, chaining reachability transitively.

    lines 36–47

    uses Reachable.rfl

        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 e010.reachable
  6. The number of edges plus one equals the number of vertices, 10 + 1 = 11.

    Rewriting the edge set with op223_weighted_eleven_edges and converting to finite set cardinalities, norm_num evaluates the size of the 10-element edge set and the 11-element vertex set, verifying 10 + 1 = 11.

    lines 48–49

    uses Nat.card_coe_set_eq, op223_weighted_eleven_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_eleven_edges, Set.ncard_coe_finset]
        norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
op223_weighted_eleven_graph
The graph op223_weighted_eleven_graph is defined from the specified set of 10 unordered pairs of vertices in Fin 11.
SimpleGraph.edgeSet_fromEdgeSet
The edge set of a graph constructed from an edge set s consists of all edges in s except self-loops (the diagonal).
Set.mem_sdiff
Membership in a set difference s \\ t means belonging to s and not belonging to t.
Sym2.mem_diagSet
Membership in Sym2.diagSet is equivalent to being a diagonal pair (a loop).
Set.mem_insert_iff
Membership in insert a s is equivalent to being equal to a or belonging to s.
Set.mem_singleton_iff
Membership in the singleton set {b} is equivalent to equality with b.
Finset.mem_coe
Coercion from Finset to Set preserves membership.
Finset.mem_insert
Membership in insert b s for a finset is equivalent to equality with b or membership in s.
Finset.mem_singleton
Membership in a singleton finset {a} is equivalent to equality with a.
And.left
From a conjunction a ∧ b, the left conjunct a holds.
SimpleGraph.fromEdgeSet_adj
Vertices v and w are adjacent in SimpleGraph.fromEdgeSet s iff the pair s(v, w) is in s and v ≠ w.
Sym2.eq
Unordered pairs s(a, b) and s(c, d) are equal iff (a = c ∧ b = d) or (a = d ∧ b = c).
SimpleGraph.isTree_iff_connected_and_card.mpr
A graph on a finite type is a tree if and only if it is connected and |E| + 1 = |V|.
SimpleGraph.connected_iff_exists_forall_reachable
A graph is connected if and only if there is a vertex that can reach every vertex.
Reachable.rfl
Every vertex is reachable from itself.
Nat.card_coe_set_eq
The cardinality of a coerced set equals its ncard.
op223_weighted_eleven_edges
The edge set of op223_weighted_eleven_graph is exactly the set of the 10 specified edges.
Set.ncard_coe_finset
The ncard of a coerced finset equals the finset cardinality.
Finset.card_insert_eq_ite
The cardinality of insert a s is s.card if a ∈ s, and s.card + 1 otherwise.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Nat.card_eq_fintype_card
For a finite type α, Nat.card α equals Fintype.card α.

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_eleven_edges : op223_weighted_eleven_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(0,10)} : Finset (Sym2 (Fin 11))) : Set (Sym2 (Fin 11))) := by  classical  rw [op223_weighted_eleven_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(0,10)} : Finset (Sym2 (Fin 11))), ¬ x.IsDiag := by decide    apply h e    simpa only [Finset.mem_insert, Finset.mem_singleton] using hetheorem op223_weighted_eleven_graph_is_tree : op223_weighted_eleven_graph.IsTree := by  classical  have e01 : op223_weighted_eleven_graph.Adj 0 1 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e12 : op223_weighted_eleven_graph.Adj 1 2 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e23 : op223_weighted_eleven_graph.Adj 2 3 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e34 : op223_weighted_eleven_graph.Adj 3 4 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e45 : op223_weighted_eleven_graph.Adj 4 5 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e06 : op223_weighted_eleven_graph.Adj 0 6 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e07 : op223_weighted_eleven_graph.Adj 0 7 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e78 : op223_weighted_eleven_graph.Adj 7 8 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e89 : op223_weighted_eleven_graph.Adj 8 9 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e010 : op223_weighted_eleven_graph.Adj 0 10 := by simp [op223_weighted_eleven_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 e010.reachable  · rw [Nat.card_coe_set_eq, op223_weighted_eleven_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