op223_example_graph_edge_01_sustainable
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
- op223_example_graphThe eight-vertex tree with edges 01, 04, 07, 12, 23, 45 and 46.
- is_sustainable_edgeAn edge e in a tree T is sustainable if there exists a non-edge f such that T - e + f is a tree and the adjacency spectral radius of T - e…
- op223_first_replacement_spectral_lowerReplacing edge 0-1 with 4-2 in the example tree yields a graph whose spectral radius is greater than 209/100.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
- op223_example_spectral_upperThe spectral radius of the eight-vertex example tree is at most 209/100.
- Arena.Reachable.transReachability is transitive.
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.
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.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical 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]
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`.
uses
SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical 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]
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.
uses
SimpleGraph.isTree_iff_connected_and_card.mprapply SimpleGraph.isTree_iff_connected_and_card.mpr constructor
`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.
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
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$.
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]
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).
uses
SimpleGraph.mem_edgeSet,SimpleGraph.fromEdgeSet_adj,Sym2.eq,Fin.ext_iffrefine ⟨?_, 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]
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.
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.
- The edge set equality in `op223_first_replacement_edges` (lines 7–13) is established by an exhaustive case analysis across all 64 pairs in `Fin 8 × Fin 8`, closed automatically by `simp`.
- The spectral radius bounds `op223_example_spectral_upper` and `op223_first_replacement_spectral_lower` are imported external theorems comparing each graph's spectral radius with the intermediate threshold 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
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.
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)