op223_nonsustainable_tree_fin_four
Every non-sustainable tree on four vertices is isomorphic to the star graph K_{1,3}.
Statement
theorem op223_nonsustainable_tree_fin_four (X : SimpleGraph (Fin 4))
(hX : is_nonsustainable_tree X) :
Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin 3))- Source
- arXiv:2610.17078, Section 3
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
- op223_tree_fin_four_iso_path_or_starEvery tree on four vertices is isomorphic either to the path graph on four vertices or to the star K_{1,3}.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
- 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.
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 2
- op223_nonsustainable_connectivity_fin_fourEvery non-sustainable tree X on Fin 4 can reach a star graph isomorphic to completeBipartiteGraph (Fin 1) (Fin 3) by a sequence of…
- op223_local_principal_maxima_not_sufficientThere is a tree on exactly three vertices with an edge uv that can be replaced by a nonedge so that the result remains a tree and has…
Read back from the Lean
For any simple graph $X$ on the vertex set Fin 4, if $X$ is a nonsustainable tree (in the sense of is_nonsustainable_tree), then $X$ is isomorphic to the complete bipartite graph $K_{1, 3}$ (completeBipartiteGraph (Fin 1) (Fin 3)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that every non-sustainable tree on four vertices is isomorphic to the star graph K₁,₃, we use the classification that every tree on four vertices is isomorphic to either the path P₄ or the star K₁,₃. We show that tree sustainability is preserved under graph isomorphism because isomorphisms preserve adjacency spectra and commute with edge deletion and insertion. We then prove that P₄ is sustainable by explicitly constructing, for each of its three edges, an edge swap that produces an isomorphic copy of P₄, thereby maintaining the tree property and achieving equality of spectral radii. Consequently, no non-sustainable tree on four vertices can be isomorphic to P₄, leaving the star graph K₁,₃ as the only possibility.
Graph isomorphism preserves the adjacency spectral radius.
By definition, the adjacency spectral radius of a graph is the spectral radius of its adjacency matrix. An isomorphism e : G ≃g H induces an algebra equivalence between matrix algebras (Matrix.reindexAlgEquiv), which preserves the spectrum by AlgEquiv.spectrum_eq. Since reindexing the adjacency matrix of G produces the adjacency matrix of H (SimpleGraph.Iso.reindex_adjMatrix), the two matrices have the same spectrum, and therefore G and H have identical spectral radii.
uses
SimpleGraph.Iso.reindex_adjMatrix,AlgEquiv.spectrum_eqclassical dsimp [adjacency_spectral_radius, spectralRadius] have hmat := SimpleGraph.Iso.reindex_adjMatrix ℝ e have hsp := AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℝ ℝ e.toEquiv) (SimpleGraph.adjMatrix ℝ G) change (Matrix.reindex e.toEquiv e.toEquiv) (SimpleGraph.adjMatrix ℝ G) = _ at hmat have hsp2 : (Matrix.reindexAlgEquiv ℝ ℝ e.toEquiv) (SimpleGraph.adjMatrix ℝ G) = (Matrix.reindex e.toEquiv e.toEquiv) (SimpleGraph.adjMatrix ℝ G) := rfl rw [hsp2, hmat] at hsp rw [hsp]
A graph isomorphism induces an isomorphism between edge-swapped graphs.
Given an isomorphism iso : G ≃g H, edge deletion and insertion commute with mapping vertices under iso. For any vertices u, v, an edge is present in (G \ {e}) ∪ {f} if and only if it is an edge of G other than e, or is f with distinct endpoints. Because iso is bijective and preserves adjacency, the mapped pair s(iso(u), iso(v)) satisfies the corresponding condition in (H \ {iso(e)}) ∪ {iso(f)}, using Set.mem_singleton_iff, Sym2.map_mk, and injectivity of iso on unordered pairs (Sym2.map.injective). Propositional logic (tauto) confirms the equivalence.
uses
Set.mem_singleton_iff,Sym2.map_mk,Sym2.map.injectiveintro u v simp only [sup_adj, deleteEdges_adj, fromEdgeSet_adj, Set.mem_singleton_iff] have h1 : H.Adj (iso u) (iso v) ↔ G.Adj u v := iso.map_rel_iff have h2 : s(iso u, iso v) = Sym2.map (⇑iso) e ↔ s(u, v) = e := by rw [← Sym2.map_mk, (Sym2.map.injective iso.injective).eq_iff] have h3 : s(iso u, iso v) = Sym2.map (⇑iso) f ↔ s(u, v) = f := by rw [← Sym2.map_mk, (Sym2.map.injective iso.injective).eq_iff] have h4 : iso u ≠ iso v ↔ u ≠ v := iso.injective.ne_iff tauto
A graph isomorphism maps every sustainable edge to a sustainable edge.
If e is a sustainable edge in G, there exists a non-edge f in Gᶜ such that swapping e for f yields a tree whose spectral radius is at least that of G. Using Sym2.ind to decompose unordered pairs, the isomorphism maps e to an edge of H and f to a non-edge of H. By op223_nonsustainable_tree_fin_four_swapIso, the swapped graph on H is isomorphic to the swapped graph on G, so it is also a tree. Finally, because graph isomorphisms preserve spectral radii (op223_nonsustainable_tree_fin_four_rad_iso), the spectral radius inequality transfers from G to H.
uses
Sym2.ind,op223_nonsustainable_tree_fin_four_swapIso,op223_nonsustainable_tree_fin_four_rad_isoclassical rcases he with ⟨he_edge, f, hf_nedge, htree, hrad⟩ have he' : Sym2.map (⇑iso) e ∈ H.edgeSet := by induction e using Sym2.ind with | _ u v => simp only [mem_edgeSet] at he_edge ⊢ exact (iso.map_rel_iff).mpr he_edge refine ⟨he', Sym2.map (⇑iso) f, ?_, ?_, ?_⟩ · induction f using Sym2.ind with | _ u v => simp only [mem_edgeSet, compl_adj] at hf_nedge ⊢ exact ⟨iso.injective.ne_iff.mpr hf_nedge.1, fun h => hf_nedge.2 (iso.map_rel_iff.mp h)⟩ · have h_iso := op223_nonsustainable_tree_fin_four_swapIso iso e f exact h_iso.isTree_iff.mp htree · have hrad_G_H : adjacency_spectral_radius G = adjacency_spectral_radius H := op223_nonsustainable_tree_fin_four_rad_iso iso have hrad_swap : adjacency_spectral_radius (G.deleteEdges {e} ⊔ fromEdgeSet {f}) = adjacency_spectral_radius (H.deleteEdges {Sym2.map iso e} ⊔ fromEdgeSet {Sym2.map iso f}) := op223_nonsustainable_tree_fin_four_rad_iso (op223_nonsustainable_tree_fin_four_swapIso iso e f) rw [← hrad_G_H, ← hrad_swap] exact hrad
Graph isomorphism preserves the property of being a sustainable tree.
Let G be a sustainable tree and let iso : G ≃g H be an isomorphism. The tree property transfers across the isomorphism. For any edge e of H, its preimage under iso.symm is an edge of G. Since G is a sustainable tree, this preimage is a sustainable edge. Applying op223_nonsustainable_tree_fin_four_is_sustainable_edge_iso pushes this edge forward under iso, showing that e is a sustainable edge of H.
uses
Sym2.ind,op223_nonsustainable_tree_fin_four_is_sustainable_edge_isorcases hG with ⟨htree, hsust⟩ refine ⟨iso.isTree_iff.mp htree, ?_⟩ intro e he have he_pre : Sym2.map iso.symm e ∈ G.edgeSet := by induction e using Sym2.ind with | _ u v => simp only [mem_edgeSet] at he ⊢ exact iso.symm.map_rel_iff.mpr he have hsust_pre := hsust (Sym2.map iso.symm e) he_pre have h_map := op223_nonsustainable_tree_fin_four_is_sustainable_edge_iso iso (Sym2.map iso.symm e) hsust_pre have h_id : Sym2.map (⇑iso) (Sym2.map (⇑iso.symm) e) = e := by induction e using Sym2.ind with | _ u v => simp rwa [h_id] at h_map
Adjacency in the swapped graph G₁ is explicitly characterized. automation
The graph G₁ is formed by deleting edge s(0, 1) from P₄ and adding edge s(0, 3). Simplifying the definitions of edge deletion, edge set addition, and graph supremum expresses adjacency between u and v as either adjacency in P₄ with s(u, v) ≠ s(0, 1), or equality s(u, v) = s(0, 3) with u ≠ v.
simp [op223_nonsustainable_tree_fin_four_G1, sup_adj, deleteEdges_adj, fromEdgeSet_adj]Adjacency in the swapped graph G₂ is explicitly characterized. automation
The graph G₂ is formed by deleting edge s(1, 2) from P₄ and adding edge s(0, 2). Simplifying the definitions expresses adjacency between u and v as either adjacency in P₄ with s(u, v) ≠ s(1, 2), or equality s(u, v) = s(0, 2) with u ≠ v.
simp [op223_nonsustainable_tree_fin_four_G2, sup_adj, deleteEdges_adj, fromEdgeSet_adj]Adjacency in the swapped graph G₃ is explicitly characterized. automation
The graph G₃ is formed by deleting edge s(2, 3) from P₄ and adding edge s(0, 3). Simplifying the definitions expresses adjacency between u and v as either adjacency in P₄ with s(u, v) ≠ s(2, 3), or equality s(u, v) = s(0, 3) with u ≠ v.
simp [op223_nonsustainable_tree_fin_four_G3, sup_adj, deleteEdges_adj, fromEdgeSet_adj]The map e₁ is a permutation of the vertices of Fin 4. automation
The mapping e₁ acts on {0, 1, 2, 3} as the cyclic shift 0 ↦ 1 ↦ 2 ↦ 3 ↦ 0. Exhaustive case analysis over all four elements of Fin 4 (fin_cases) verifies that the candidate inverse is both a left and right inverse.
by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩
The permutation e₁ is a graph isomorphism between P₄ and G₁. automation
To show that e₁ is an isomorphism between P₄ and G₁, it suffices to check that G₁ contains edge s(e₁(u), e₁(v)) if and only if P₄ contains edge s(u, v). Exhaustive case analysis over all 16 pairs (u, v) via fin_cases and boolean evaluation (decide) confirms this equivalence.
intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e1, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G1_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)
The map e₂ is a permutation of the vertices of Fin 4. automation
The mapping e₂ swaps 0 and 1 while fixing 2 and 3. Exhaustive case analysis over all four elements verifies that it is its own two-sided inverse.
by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩
The permutation e₂ is a graph isomorphism between P₄ and G₂. automation
Exhaustive case analysis over all 16 vertex pairs (u, v) via fin_cases and decide verifies that e₂ preserves adjacency between P₄ and G₂.
intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e2, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G2_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)
The map e₃ is a permutation of the vertices of Fin 4. automation
The mapping e₃ swaps 0 and 2 while fixing 1 and 3. Exhaustive case analysis over all four elements verifies that it is its own two-sided inverse.
by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩
The permutation e₃ is a graph isomorphism between P₄ and G₃. automation
Exhaustive case analysis over all 16 vertex pairs (u, v) via fin_cases and decide verifies that e₃ preserves adjacency between P₄ and G₃.
intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e3, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G3_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)
The edges of P₄ are precisely s(0, 1), s(1, 2), and s(2, 3). automation
Any edge e of P₄ is an unordered pair s(u, v) by Sym2.ind. Testing all pairs of vertices in Fin 4 reveals that adjacency holds only when {u, v} is {0, 1}, {1, 2}, or {2, 3}.
uses
Sym2.indinduction e using Sym2.ind with | _ u v => rw [mem_edgeSet, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj] at he fin_cases u <;> fin_cases v <;> simp_all
The pair s(0, 3) is a non-edge of P₄. automation
Deciding adjacency in the complement graph via decide confirms that 0 ≠ 3 and 0 is not adjacent to 3 in P₄.
simp only [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj, op223_nonsustainable_tree_fin_four_P4, SimpleGraph.pathGraph_adj] decide
The pair s(0, 2) is a non-edge of P₄. automation
Deciding adjacency in the complement graph via decide confirms that 0 ≠ 2 and 0 is not adjacent to 2 in P₄.
simp only [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj, op223_nonsustainable_tree_fin_four_P4, SimpleGraph.pathGraph_adj] decide
The path graph P₄ is a sustainable tree.
Assuming P₄ is a tree, we show that every edge e ∈ E(P₄) is sustainable. By op223_nonsustainable_tree_fin_four_P4_edges, e is either s(0, 1), s(1, 2), or s(2, 3). For e = s(0, 1), swapping for non-edge s(0, 3) (op223_nonsustainable_tree_fin_four_03_compl) yields G₁, which is isomorphic to P₄ via op223_nonsustainable_tree_fin_four_iso1. Thus G₁ is a tree, and by op223_nonsustainable_tree_fin_four_rad_iso, its spectral radius equals that of P₄, satisfying the inequality with equality. For e = s(1, 2), swapping for non-edge s(0, 2) (op223_nonsustainable_tree_fin_four_02_compl) yields G₂ ≅ P₄ via op223_nonsustainable_tree_fin_four_iso2, again producing a tree of equal spectral radius. For e = s(2, 3), swapping for s(0, 3) yields G₃ ≅ P₄ via op223_nonsustainable_tree_fin_four_iso3, also producing a tree of equal spectral radius. Hence all edges of P₄ are sustainable.
uses
op223_nonsustainable_tree_fin_four_P4_edges,op223_nonsustainable_tree_fin_four_03_compl,op223_nonsustainable_tree_fin_four_iso1,op223_nonsustainable_tree_fin_four_rad_iso,op223_nonsustainable_tree_fin_four_02_compl,op223_nonsustainable_tree_fin_four_iso2,op223_nonsustainable_tree_fin_four_iso3refine ⟨hP4_tree, ?_⟩ intro e he rcases op223_nonsustainable_tree_fin_four_P4_edges e he with rfl | rfl | rfl · refine ⟨he, s(0, 3), op223_nonsustainable_tree_fin_four_03_compl, op223_nonsustainable_tree_fin_four_iso1.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G1 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso1] · refine ⟨he, s(0, 2), op223_nonsustainable_tree_fin_four_02_compl, op223_nonsustainable_tree_fin_four_iso2.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G2 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso2] · refine ⟨he, s(0, 3), op223_nonsustainable_tree_fin_four_03_compl, op223_nonsustainable_tree_fin_four_iso3.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G3 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso3]
Every non-sustainable tree on four vertices is isomorphic to the star graph K₁,₃.
By the classification of trees on four vertices (op223_tree_fin_four_iso_path_or_star), any tree X on four vertices is isomorphic to either the path P₄ or the star graph completeBipartiteGraph (Fin 1) (Fin 3). If X ≃g P₄, then P₄ is a tree, so P₄ is sustainable by op223_nonsustainable_tree_fin_four_P4_sustainable. By op223_nonsustainable_tree_fin_four_is_sustainable_tree_iso, sustainability transfers across the isomorphism to X, contradicting the assumption that X is non-sustainable. Therefore, the path case leads to a contradiction (exfalso), leaving the star graph as the only possibility.
uses
op223_tree_fin_four_iso_path_or_star,op223_nonsustainable_tree_fin_four_P4_sustainable,op223_nonsustainable_tree_fin_four_is_sustainable_tree_isorcases op223_tree_fin_four_iso_path_or_star X hX.1 with ⟨⟨iso_path⟩⟩ | hstar · exfalso have htree_P4 : op223_nonsustainable_tree_fin_four_P4.IsTree := iso_path.isTree_iff.mp hX.1 have hsust_P4 : is_sustainable_tree op223_nonsustainable_tree_fin_four_P4 := op223_nonsustainable_tree_fin_four_P4_sustainable htree_P4 have hsust_X : is_sustainable_tree X := op223_nonsustainable_tree_fin_four_is_sustainable_tree_iso iso_path.symm hsust_P4 exact hX.2 hsust_X · exact hstar
AlgEquiv.spectrum_eq- An algebra equivalence between algebras preserves the spectrum of any element.
Set.mem_singleton_iff- An element belongs to a singleton set if and only if it is equal to the singleton's unique element.
SimpleGraph.Iso.reindex_adjMatrix- For any graph isomorphism, reindexing the adjacency matrix of the domain yields the adjacency matrix of the codomain.
Sym2.ind- Every element of the symmetric square Sym²(α) can be represented as an unordered pair s(x, y).
Sym2.map.injective- If a function is injective, its induced map on unordered pairs is also injective.
Sym2.map_mk- The image of an unordered pair s(a, b) under Sym2.map f is the unordered pair s(f a, f b).
op223_nonsustainable_tree_fin_four_02_compl- The pair s(0, 2) is a non-edge (an edge of the complement graph) of the path graph P₄.
op223_nonsustainable_tree_fin_four_03_compl- The pair s(0, 3) is a non-edge (an edge of the complement graph) of the path graph P₄.
op223_nonsustainable_tree_fin_four_P4_edges- Every edge of the path graph P₄ on four vertices is either s(0, 1), s(1, 2), or s(2, 3).
op223_nonsustainable_tree_fin_four_P4_sustainable- The path graph P₄ is a sustainable tree.
op223_nonsustainable_tree_fin_four_is_sustainable_edge_iso- A graph isomorphism maps every sustainable edge of G to a sustainable edge of H.
op223_nonsustainable_tree_fin_four_is_sustainable_tree_iso- Graph isomorphism preserves the property of being a sustainable tree.
op223_nonsustainable_tree_fin_four_iso1- The path graph P₄ is isomorphic to G₁, the graph obtained by swapping edge s(0, 1) for s(0, 3).
op223_nonsustainable_tree_fin_four_iso2- The path graph P₄ is isomorphic to G₂, the graph obtained by swapping edge s(1, 2) for s(0, 2).
op223_nonsustainable_tree_fin_four_iso3- The path graph P₄ is isomorphic to G₃, the graph obtained by swapping edge s(2, 3) for s(0, 3).
op223_nonsustainable_tree_fin_four_rad_iso- Isomorphic simple graphs have identical adjacency spectral radii.
op223_nonsustainable_tree_fin_four_swapIso- A graph isomorphism G ≃g H induces an isomorphism between the edge-swapped graphs (G \ {e}) ∪ {f} and (H \ {iso(e)}) ∪ {iso(f)}.
op223_tree_fin_four_iso_path_or_star- Every tree on four vertices is isomorphic to either the path graph P₄ or the star graph K₁,₃.
- The isomorphisms between the edge-swapped graphs G₁, G₂, G₃ and the path graph P₄, as well as the edge and non-edge characterizations on Fin 4, are established by exhaustive finite verification over all vertex pairs using fin_cases and the decision procedure decide.
- Spectral radius invariance under graph isomorphism is proved algebraically by observing that reindexing along the vertex equivalence induces an algebra equivalence on matrix algebras, which preserves the matrix spectrum.
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 SimpleGraphtheorem op223_nonsustainable_tree_fin_four_rad_iso {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] {G : SimpleGraph V} {H : SimpleGraph W} (e : G ≃g H) : adjacency_spectral_radius G = adjacency_spectral_radius H := by classical dsimp [adjacency_spectral_radius, spectralRadius] have hmat := SimpleGraph.Iso.reindex_adjMatrix ℝ e have hsp := AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℝ ℝ e.toEquiv) (SimpleGraph.adjMatrix ℝ G) change (Matrix.reindex e.toEquiv e.toEquiv) (SimpleGraph.adjMatrix ℝ G) = _ at hmat have hsp2 : (Matrix.reindexAlgEquiv ℝ ℝ e.toEquiv) (SimpleGraph.adjMatrix ℝ G) = (Matrix.reindex e.toEquiv e.toEquiv) (SimpleGraph.adjMatrix ℝ G) := rfl rw [hsp2, hmat] at hsp rw [hsp]def op223_nonsustainable_tree_fin_four_swapIso {V W : Type*} {G : SimpleGraph V} {H : SimpleGraph W} (iso : G ≃g H) (e f : Sym2 V) : (G.deleteEdges {e} ⊔ fromEdgeSet {f}) ≃g (H.deleteEdges {Sym2.map iso e} ⊔ fromEdgeSet {Sym2.map iso f}) where toEquiv := iso.toEquiv map_rel_iff' := by intro u v simp only [sup_adj, deleteEdges_adj, fromEdgeSet_adj, Set.mem_singleton_iff] have h1 : H.Adj (iso u) (iso v) ↔ G.Adj u v := iso.map_rel_iff have h2 : s(iso u, iso v) = Sym2.map (⇑iso) e ↔ s(u, v) = e := by rw [← Sym2.map_mk, (Sym2.map.injective iso.injective).eq_iff] have h3 : s(iso u, iso v) = Sym2.map (⇑iso) f ↔ s(u, v) = f := by rw [← Sym2.map_mk, (Sym2.map.injective iso.injective).eq_iff] have h4 : iso u ≠ iso v ↔ u ≠ v := iso.injective.ne_iff tautotheorem op223_nonsustainable_tree_fin_four_is_sustainable_edge_iso {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] {G : SimpleGraph V} {H : SimpleGraph W} (iso : G ≃g H) (e : Sym2 V) (he : is_sustainable_edge G e) : is_sustainable_edge H (Sym2.map iso e) := by classical rcases he with ⟨he_edge, f, hf_nedge, htree, hrad⟩ have he' : Sym2.map (⇑iso) e ∈ H.edgeSet := by induction e using Sym2.ind with | _ u v => simp only [mem_edgeSet] at he_edge ⊢ exact (iso.map_rel_iff).mpr he_edge refine ⟨he', Sym2.map (⇑iso) f, ?_, ?_, ?_⟩ · induction f using Sym2.ind with | _ u v => simp only [mem_edgeSet, compl_adj] at hf_nedge ⊢ exact ⟨iso.injective.ne_iff.mpr hf_nedge.1, fun h => hf_nedge.2 (iso.map_rel_iff.mp h)⟩ · have h_iso := op223_nonsustainable_tree_fin_four_swapIso iso e f exact h_iso.isTree_iff.mp htree · have hrad_G_H : adjacency_spectral_radius G = adjacency_spectral_radius H := op223_nonsustainable_tree_fin_four_rad_iso iso have hrad_swap : adjacency_spectral_radius (G.deleteEdges {e} ⊔ fromEdgeSet {f}) = adjacency_spectral_radius (H.deleteEdges {Sym2.map iso e} ⊔ fromEdgeSet {Sym2.map iso f}) := op223_nonsustainable_tree_fin_four_rad_iso (op223_nonsustainable_tree_fin_four_swapIso iso e f) rw [← hrad_G_H, ← hrad_swap] exact hradtheorem op223_nonsustainable_tree_fin_four_is_sustainable_tree_iso {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] {G : SimpleGraph V} {H : SimpleGraph W} (iso : G ≃g H) (hG : is_sustainable_tree G) : is_sustainable_tree H := by rcases hG with ⟨htree, hsust⟩ refine ⟨iso.isTree_iff.mp htree, ?_⟩ intro e he have he_pre : Sym2.map iso.symm e ∈ G.edgeSet := by induction e using Sym2.ind with | _ u v => simp only [mem_edgeSet] at he ⊢ exact iso.symm.map_rel_iff.mpr he have hsust_pre := hsust (Sym2.map iso.symm e) he_pre have h_map := op223_nonsustainable_tree_fin_four_is_sustainable_edge_iso iso (Sym2.map iso.symm e) hsust_pre have h_id : Sym2.map (⇑iso) (Sym2.map (⇑iso.symm) e) = e := by induction e using Sym2.ind with | _ u v => simp rwa [h_id] at h_mapdef op223_nonsustainable_tree_fin_four_P4 : SimpleGraph (Fin 4) := pathGraph 4def op223_nonsustainable_tree_fin_four_G1 : SimpleGraph (Fin 4) := op223_nonsustainable_tree_fin_four_P4.deleteEdges {s(0, 1)} ⊔ fromEdgeSet {s(0, 3)}def op223_nonsustainable_tree_fin_four_G2 : SimpleGraph (Fin 4) := op223_nonsustainable_tree_fin_four_P4.deleteEdges {s(1, 2)} ⊔ fromEdgeSet {s(0, 2)}def op223_nonsustainable_tree_fin_four_G3 : SimpleGraph (Fin 4) := op223_nonsustainable_tree_fin_four_P4.deleteEdges {s(2, 3)} ⊔ fromEdgeSet {s(0, 3)}lemma op223_nonsustainable_tree_fin_four_G1_adj (u v : Fin 4) : op223_nonsustainable_tree_fin_four_G1.Adj u v ↔ (op223_nonsustainable_tree_fin_four_P4.Adj u v ∧ s(u, v) ≠ s(0, 1)) ∨ (s(u, v) = s(0, 3) ∧ u ≠ v) := by simp [op223_nonsustainable_tree_fin_four_G1, sup_adj, deleteEdges_adj, fromEdgeSet_adj]lemma op223_nonsustainable_tree_fin_four_G2_adj (u v : Fin 4) : op223_nonsustainable_tree_fin_four_G2.Adj u v ↔ (op223_nonsustainable_tree_fin_four_P4.Adj u v ∧ s(u, v) ≠ s(1, 2)) ∨ (s(u, v) = s(0, 2) ∧ u ≠ v) := by simp [op223_nonsustainable_tree_fin_four_G2, sup_adj, deleteEdges_adj, fromEdgeSet_adj]lemma op223_nonsustainable_tree_fin_four_G3_adj (u v : Fin 4) : op223_nonsustainable_tree_fin_four_G3.Adj u v ↔ (op223_nonsustainable_tree_fin_four_P4.Adj u v ∧ s(u, v) ≠ s(2, 3)) ∨ (s(u, v) = s(0, 3) ∧ u ≠ v) := by simp [op223_nonsustainable_tree_fin_four_G3, sup_adj, deleteEdges_adj, fromEdgeSet_adj]def op223_nonsustainable_tree_fin_four_e1 : Fin 4 ≃ Fin 4 := ⟨fun x => match x with | 0 => 1 | 1 => 2 | 2 => 3 | 3 => 0, fun x => match x with | 1 => 0 | 2 => 1 | 3 => 2 | 0 => 3, by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩theorem op223_nonsustainable_tree_fin_four_G1_iso_P4 : ∀ u v : Fin 4, op223_nonsustainable_tree_fin_four_G1.Adj (op223_nonsustainable_tree_fin_four_e1 u) (op223_nonsustainable_tree_fin_four_e1 v) ↔ op223_nonsustainable_tree_fin_four_P4.Adj u v := by intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e1, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G1_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)def op223_nonsustainable_tree_fin_four_iso1 : op223_nonsustainable_tree_fin_four_P4 ≃g op223_nonsustainable_tree_fin_four_G1 where toEquiv := op223_nonsustainable_tree_fin_four_e1 map_rel_iff' {u v} := op223_nonsustainable_tree_fin_four_G1_iso_P4 u vdef op223_nonsustainable_tree_fin_four_e2 : Fin 4 ≃ Fin 4 := ⟨fun x => match x with | 0 => 1 | 1 => 0 | 2 => 2 | 3 => 3, fun x => match x with | 1 => 0 | 0 => 1 | 2 => 2 | 3 => 3, by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩theorem op223_nonsustainable_tree_fin_four_G2_iso_P4 : ∀ u v : Fin 4, op223_nonsustainable_tree_fin_four_G2.Adj (op223_nonsustainable_tree_fin_four_e2 u) (op223_nonsustainable_tree_fin_four_e2 v) ↔ op223_nonsustainable_tree_fin_four_P4.Adj u v := by intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e2, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G2_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)def op223_nonsustainable_tree_fin_four_iso2 : op223_nonsustainable_tree_fin_four_P4 ≃g op223_nonsustainable_tree_fin_four_G2 where toEquiv := op223_nonsustainable_tree_fin_four_e2 map_rel_iff' {u v} := op223_nonsustainable_tree_fin_four_G2_iso_P4 u vdef op223_nonsustainable_tree_fin_four_e3 : Fin 4 ≃ Fin 4 := ⟨fun x => match x with | 0 => 2 | 1 => 1 | 2 => 0 | 3 => 3, fun x => match x with | 2 => 0 | 1 => 1 | 0 => 2 | 3 => 3, by intro x; fin_cases x <;> rfl, by intro x; fin_cases x <;> rfl⟩theorem op223_nonsustainable_tree_fin_four_G3_iso_P4 : ∀ u v : Fin 4, op223_nonsustainable_tree_fin_four_G3.Adj (op223_nonsustainable_tree_fin_four_e3 u) (op223_nonsustainable_tree_fin_four_e3 v) ↔ op223_nonsustainable_tree_fin_four_P4.Adj u v := by intro u v fin_cases u <;> fin_cases v <;> (simp only [op223_nonsustainable_tree_fin_four_e3, Equiv.coe_fn_mk, op223_nonsustainable_tree_fin_four_G3_adj, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj]; decide)def op223_nonsustainable_tree_fin_four_iso3 : op223_nonsustainable_tree_fin_four_P4 ≃g op223_nonsustainable_tree_fin_four_G3 where toEquiv := op223_nonsustainable_tree_fin_four_e3 map_rel_iff' {u v} := op223_nonsustainable_tree_fin_four_G3_iso_P4 u vlemma op223_nonsustainable_tree_fin_four_P4_edges (e : Sym2 (Fin 4)) (he : e ∈ op223_nonsustainable_tree_fin_four_P4.edgeSet) : e = s(0, 1) ∨ e = s(1, 2) ∨ e = s(2, 3) := by induction e using Sym2.ind with | _ u v => rw [mem_edgeSet, op223_nonsustainable_tree_fin_four_P4, pathGraph_adj] at he fin_cases u <;> fin_cases v <;> simp_alllemma op223_nonsustainable_tree_fin_four_03_compl : s((0 : Fin 4), (3 : Fin 4)) ∈ op223_nonsustainable_tree_fin_four_P4ᶜ.edgeSet := by simp only [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj, op223_nonsustainable_tree_fin_four_P4, SimpleGraph.pathGraph_adj] decidelemma op223_nonsustainable_tree_fin_four_02_compl : s((0 : Fin 4), (2 : Fin 4)) ∈ op223_nonsustainable_tree_fin_four_P4ᶜ.edgeSet := by simp only [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj, op223_nonsustainable_tree_fin_four_P4, SimpleGraph.pathGraph_adj] decidetheorem op223_nonsustainable_tree_fin_four_P4_sustainable (hP4_tree : op223_nonsustainable_tree_fin_four_P4.IsTree) : is_sustainable_tree op223_nonsustainable_tree_fin_four_P4 := by refine ⟨hP4_tree, ?_⟩ intro e he rcases op223_nonsustainable_tree_fin_four_P4_edges e he with rfl | rfl | rfl · refine ⟨he, s(0, 3), op223_nonsustainable_tree_fin_four_03_compl, op223_nonsustainable_tree_fin_four_iso1.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G1 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso1] · refine ⟨he, s(0, 2), op223_nonsustainable_tree_fin_four_02_compl, op223_nonsustainable_tree_fin_four_iso2.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G2 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso2] · refine ⟨he, s(0, 3), op223_nonsustainable_tree_fin_four_03_compl, op223_nonsustainable_tree_fin_four_iso3.isTree_iff.mp hP4_tree, ?_⟩ change adjacency_spectral_radius op223_nonsustainable_tree_fin_four_P4 ≤ adjacency_spectral_radius op223_nonsustainable_tree_fin_four_G3 rw [op223_nonsustainable_tree_fin_four_rad_iso op223_nonsustainable_tree_fin_four_iso3]/-- Every non-sustainable tree on 4 vertices is isomorphic to the star completeBipartiteGraph (Fin 1) (Fin 3). -/theorem op223_nonsustainable_tree_fin_four (X : SimpleGraph (Fin 4)) (hX : is_nonsustainable_tree X) : Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin 3)) := by rcases op223_tree_fin_four_iso_path_or_star X hX.1 with ⟨⟨iso_path⟩⟩ | hstar · exfalso have htree_P4 : op223_nonsustainable_tree_fin_four_P4.IsTree := iso_path.isTree_iff.mp hX.1 have hsust_P4 : is_sustainable_tree op223_nonsustainable_tree_fin_four_P4 := op223_nonsustainable_tree_fin_four_P4_sustainable htree_P4 have hsust_X : is_sustainable_tree X := op223_nonsustainable_tree_fin_four_is_sustainable_tree_iso iso_path.symm hsust_P4 exact hX.2 hsust_X · exact hstar