AFTD Auto-Formalizing Theoretical Domains

op223_example_graph_edge_01_sustainable

theoremverified

Edge 0-1 in op223_example_graph is sustainable.

Statement

theorem op223_example_graph_edge_01_sustainable : is_sustainable_edge op223_example_graph s(0, 1)
Source
step towards op223_example_graph_sustainable
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

To prove that edge $\{0, 1\}$ in the 8-vertex tree `op223_example_graph` is sustainable, the proof exhibits $\{4, 2\}$ as a replacement edge. It first establishes that the replacement graph (obtained by deleting $\{0, 1\}$ and inserting $\{4, 2\}$) is a tree by showing it is connected (every vertex is reachable from 0) and has 7 edges on 8 vertices. Finally, it combines the known upper bound $\rho(G) \le 2.09$ for the original tree with the lower bound $\rho(G') > 2.09$ for the replacement tree to conclude that replacing $\{0, 1\}$ with $\{4, 2\}$ does not decrease the adjacency spectral radius.

  1. The edge set of `example_witness_graph` consists precisely of the seven undirected pairs {0, 4}, {0, 7}, {1, 2}, {2, 3}, {2, 4}, {4, 5}, and {4, 6}.

    By set extensionality and induction on unordered pairs (`Sym2.ind`), every edge is of the form $s(a, b)$ for vertices $a, b \in \text{Fin } 8$. Exhausting all 64 pairs $(a, b)$ with `fin_cases`, each case is resolved by simplifying the definitions of graph union, edge deletion, and edge set creation.

    lines 7–13

    uses Sym2.ind, SimpleGraph.mem_edgeSet, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq

      classical
      ext e
      induction e using Sym2.ind with
      | _ a b =>
        fin_cases a <;> fin_cases b <;>
          simp [example_witness_graph, op223_example_graph, SimpleGraph.mem_edgeSet,
            SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
  2. The replacement graph `example_witness_graph` contains the adjacencies (0, 4), (0, 7), (1, 2), (2, 3), (2, 4), (4, 5), and (4, 6).

    Each of the seven adjacency relations is established individually by expanding the definitions of edge deletion, edge set creation, and graph union on `example_witness_graph`.

    lines 16–23

    uses SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq

      classical
      have e04 : example_witness_graph.Adj 0 4 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e07 : example_witness_graph.Adj 0 7 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e12 : example_witness_graph.Adj 1 2 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e23 : example_witness_graph.Adj 2 3 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e24 : example_witness_graph.Adj 2 4 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e45 : example_witness_graph.Adj 4 5 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e46 : example_witness_graph.Adj 4 6 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
  3. To show that `example_witness_graph` is a tree, it suffices to show that it is connected and that its number of edges plus one equals its number of vertices (8).

    We apply the characterization of finite trees as connected graphs with $|E| + 1 = |V|$ (`SimpleGraph.isTree_iff_connected_and_card.mpr`) and split the goal into the connectivity subgoal and the cardinality equality.

    lines 24–25

    uses SimpleGraph.isTree_iff_connected_and_card.mpr

      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
  4. `example_witness_graph` is connected.

    Using the criterion that a graph is connected if some vertex can reach all others (`SimpleGraph.connected_iff_exists_forall_reachable`), we choose vertex 0. For each of the 8 vertices in `Fin 8`, vertex 0 reaches itself reflexively (`Reachable.rfl`), reaches 4 and 7 directly by single edges, and reaches 1, 2, 3, 5, and 6 by concatenating the known edges into paths.

    lines 26–36

    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 (e04.reachable.trans e24.symm.reachable).trans e12.symm.reachable
        · exact e04.reachable.trans e24.symm.reachable
        · exact (e04.reachable.trans e24.symm.reachable).trans e23.reachable
        · exact e04.reachable
        · exact e04.reachable.trans e45.reachable
        · exact e04.reachable.trans e46.reachable
        · exact e07.reachable
  5. The edge count of `example_witness_graph` plus one equals 8, completing the proof that `example_witness_graph` is a tree.

    Rewriting the edge set using the explicit 7-element description (`op223_first_replacement_edges`), the calculation reduces to evaluating the size of a 7-element set, which arithmetic normalization (`norm_num`) computes to $7 + 1 = 8$.

    lines 37–38

    uses Nat.card_coe_set_eq, op223_first_replacement_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_first_replacement_edges, Set.ncard_coe_finset]
        norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
  6. The edge $s(0, 1)$ belongs to `op223_example_graph`, and $s(4, 2)$ is a non-edge, making $s(4, 2)$ a valid replacement candidate to witness sustainability.

    We supply $s(4, 2)$ as the replacement edge candidate using `refine`. Simplifying with the definition of `op223_example_graph` confirms that $s(0, 1)$ is an edge of the original graph and that $s(4, 2)$ is not an edge (belonging to the complement graph).

    lines 42–44

    uses SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff

      refine ⟨?_, s(4,2), ?_, ?_, ?_⟩
      · simp [SimpleGraph.mem_edgeSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      · simp [SimpleGraph.mem_edgeSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff]
  7. The replacement graph is a tree and its adjacency spectral radius is at least that of the original graph, concluding that edge $s(0, 1)$ is sustainable.

    The replacement graph is a tree by `op223_first_replacement_tree`. The spectral radius of `op223_example_graph` is at most 2.09 (`op223_example_spectral_upper`), while the replacement graph has spectral radius strictly greater than 2.09 (`op223_first_replacement_spectral_lower`). Weakening the strict inequality (`le_of_lt`) and applying transitivity (`le_trans`) shows the spectral radius does not decrease.

    lines 45–46

    uses op223_first_replacement_tree, le_trans, op223_example_spectral_upper, le_of_lt, op223_first_replacement_spectral_lower

      · exact op223_first_replacement_tree
      · exact le_trans op223_example_spectral_upper (le_of_lt op223_first_replacement_spectral_lower)
Sym2.ind
A property holds for every unordered pair in `Sym2 α` if it holds for every pair of the form `s(x, y)`.
SimpleGraph.mem_edgeSet
An unordered pair `s(v, w)` belongs to the edge set of a simple graph if and only if `v` and `w` are adjacent.
SimpleGraph.sup_adj
Two vertices are adjacent in the union of two graphs if and only if they are adjacent in at least one of the graphs.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in a graph with edge set `s` deleted if and only if they were adjacent in the original graph and the pair does not belong to `s`.
SimpleGraph.fromEdgeSet_adj
Two distinct vertices are adjacent in the graph constructed from an edge set `s` if and only if their pair belongs to `s`.
Sym2.eq
Two unordered pairs `s(a, b)` and `s(c, d)` are equal if and only if either `a = c` and `b = d`, or `a = d` and `b = c`.
SimpleGraph.isTree_iff_connected_and_card.mpr
A simple graph on vertex set `V` is a tree if it is connected and its number of edges plus one equals the number of vertices.
SimpleGraph.connected_iff_exists_forall_reachable
A graph is connected if and only if there exists a vertex from which every vertex is reachable.
Reachable.rfl
Every vertex in a graph is reachable from itself.
Nat.card_coe_set_eq
The cardinality of a coerced set type equals the noncomputable cardinality of the set.
op223_first_replacement_edges
The edge set of `example_witness_graph` consists precisely of the seven pairs {0, 4}, {0, 7}, {1, 2}, {2, 3}, {2, 4}, {4, 5}, and {4, 6}.
Set.ncard_coe_finset
The noncomputable cardinality of a finite set coerced to a set equals its `Finset.card`.
Finset.card_insert_eq_ite
Inserting an element into a finite set increases its size by 1 if the element is not already present, and preserves it 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 any finite type, `Nat.card` equals `Fintype.card`.
op223_first_replacement_tree
The replacement graph `example_witness_graph` is a tree.
le_trans
If `a ≤ b` and `b ≤ c`, then `a ≤ c`.
op223_example_spectral_upper
The adjacency spectral radius of `op223_example_graph` is at most 2.09.
le_of_lt
Strict inequality `a < b` implies non-strict inequality `a ≤ b`.
op223_first_replacement_spectral_lower
The adjacency spectral radius of the replacement graph is strictly greater than 2.09.

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 Classical ENNRealset_option maxHeartbeats 5000000 inlemma op223_first_replacement_edges : example_witness_graph.edgeSet =    (({s(0,4), s(0,7), s(1,2), s(2,3), s(2,4), s(4,5), s(4,6)} : Finset (Sym2 (Fin 8))) : Set (Sym2 (Fin 8))) := by  classical  ext e  induction e using Sym2.ind with  | _ a b =>    fin_cases a <;> fin_cases b <;>      simp [example_witness_graph, op223_example_graph, SimpleGraph.mem_edgeSet,        SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]theorem op223_first_replacement_tree : example_witness_graph.IsTree := by  classical  have e04 : example_witness_graph.Adj 0 4 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e07 : example_witness_graph.Adj 0 7 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e12 : example_witness_graph.Adj 1 2 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e23 : example_witness_graph.Adj 2 3 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e24 : example_witness_graph.Adj 2 4 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e45 : example_witness_graph.Adj 4 5 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e46 : example_witness_graph.Adj 4 6 := by simp [example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, 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 (e04.reachable.trans e24.symm.reachable).trans e12.symm.reachable    · exact e04.reachable.trans e24.symm.reachable    · exact (e04.reachable.trans e24.symm.reachable).trans e23.reachable    · exact e04.reachable    · exact e04.reachable.trans e45.reachable    · exact e04.reachable.trans e46.reachable    · exact e07.reachable  · rw [Nat.card_coe_set_eq, op223_first_replacement_edges, Set.ncard_coe_finset]    norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]/-- Edge 0-1 in op223_example_graph is sustainable. -/theorem op223_example_graph_edge_01_sustainable : is_sustainable_edge op223_example_graph s(0, 1) := by  refine ⟨?_, s(4,2), ?_, ?_, ?_⟩  · simp [SimpleGraph.mem_edgeSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  · simp [SimpleGraph.mem_edgeSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff]  · exact op223_first_replacement_tree  · exact le_trans op223_example_spectral_upper (le_of_lt op223_first_replacement_spectral_lower)
See it in the graphDiscuss this resultChallenge it