/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import Mathlib.Combinatorics.SimpleGraph.Acyclic public import Mathlib.Combinatorics.SimpleGraph.Basic public import Mathlib.Combinatorics.SimpleGraph.Finite public import Mathlib.Combinatorics.SimpleGraph.Girth public import Mathlib.Data.Set.Finite.Lemmas@[expose] public section

Largest induced tree

This file defines largestInducedTreeSize, the number of vertices in a largest induced subtree of a graph.

namespace SimpleGraphvariable {α : Type*} [Fintype α] [DecidableEq α]

largestInducedTreeSize G is the number of vertices in a largest induced subtree of G. A tree is a connected acyclic graph; an induced tree is an induced subgraph that is a tree.

noncomputable def largestInducedTreeSize (G : SimpleGraph α) : ℕ := sSup { n | ∃ s : Finset α, s.card = n ∧ (G.induce (s : Set α)).IsTree }omit [DecidableEq α] in

The order of any induced tree is bounded by largestInducedTreeSize.

lemma card_le_largestInducedTreeSize {G : SimpleGraph α} {s : Finset α} (hs : (G.induce (s : Set α)).IsTree) : s.card ≤ largestInducedTreeSize G := α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ s.card ≤ G.largestInducedTreeSize α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ s.card ≤ sSup {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree} α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ BddAbove {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree}α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ s.card ∈ {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree} α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ BddAbove {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree} α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ Fintype.card α ∈ upperBounds {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree} α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTreen:ℕhn:n ∈ {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree}⊢ n ≤ Fintype.card α α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTreet:Finset αright✝:(induce (↑t) G).IsTree⊢ t.card ≤ Fintype.card α All goals completed! 🐙 α:Type u_1inst✝:Fintype αG:SimpleGraph αs:Finset αhs:(induce (↑s) G).IsTree⊢ s.card ∈ {n | ∃ s, s.card = n ∧ (induce (↑s) G).IsTree} All goals completed! 🐙omit [DecidableEq α] in

Every finite graph with a vertex has a nonempty induced tree.

α:Type u_1inst✝¹:Fintype αG:SimpleGraph αinst✝:Nonempty αx:α := Classical.choice ⋯s:Finset α := {x}hs:↑s = {x}hT:(induce (↑s) G).IsTree⊢ 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αG:SimpleGraph αinst✝:Nonempty αx:α := Classical.choice ⋯s:Finset α := {x}hs:↑s = {x}hT:(induce (↑s) G).IsTreehle:s.card ≤ G.largestInducedTreeSize⊢ 1 ≤ G.largestInducedTreeSize All goals completed! 🐙omit [Fintype α] in

Attaching a new vertex along its unique neighbor in an induced tree gives a larger induced tree.

α:Type u_1inst✝:DecidableEq αG:SimpleGraph αs:Finset αz:αa:αhT:(induce (↑s) G).IsTree_hz:z ∉ sha:a ∈ shza:G.Adj z ahuniq:∀ ⦃b : α⦄, b ∈ s → G.Adj z b → b = av:↑↑(insert z s)c:(induce (↑(insert z s)) G).Walk v vhc:c.IsCyclee:induce (↑(insert z s)) G ↪g G := Embedding.induce ↑(insert z s)q:G.Walk (e v) (e v) := Walk.map e.toHom chq:q.IsCyclehq_mem:∀ w ∈ q.support, w ∈ insert z shzq:z ∉ q.supporthqs:∀ w ∈ q.support, w ∈ ↑sqi:(induce (↑s) G).Walk ⟨e v, ⋯⟩ ⟨e v, ⋯⟩ := Walk.induce (↑s) q hqshqi:qi.IsCycle⊢ False All goals completed! 🐙omit [Fintype α] in

A shortest walk induces a tree on its support.

α:Type u_1inst✝:DecidableEq αG:SimpleGraph αu✝:αv✝:αu:αv:αw:αhuv:G.Adj u vp:G.Walk v wih:p.length = G.dist v w → (induce (↑p.support.toFinset) G).IsTreehp:(cons huv p).length = G.dist u whptail:p.length = G.dist v whT:(induce (↑p.support.toFinset) G).IsTreehpath:(cons huv p).IsPathhu_not:u ∉ p.support.toFinsethuniq:∀ ⦃b : α⦄, b ∈ p.support.toFinset → G.Adj u b → b = vhsupp:(cons huv p).support.toFinset = insert u p.support.toFinset⊢ (induce (↑(insert u p.support.toFinset)) G).IsTree exact hT.induce_insert_of_unique_adj hu_not (α:Type u_1inst✝:DecidableEq αG:SimpleGraph αu✝:αv✝:αu:αv:αw:αhuv:G.Adj u vp:G.Walk v wih:p.length = G.dist v w → (induce (↑p.support.toFinset) G).IsTreehp:(cons huv p).length = G.dist u whptail:p.length = G.dist v whT:(induce (↑p.support.toFinset) G).IsTreehpath:(cons huv p).IsPathhu_not:u ∉ p.support.toFinsethuniq:∀ ⦃b : α⦄, b ∈ p.support.toFinset → G.Adj u b → b = vhsupp:(cons huv p).support.toFinset = insert u p.support.toFinset⊢ v ∈ p.support.toFinset All goals completed! 🐙) huv huniq

Removing one vertex from a shortest cycle gives an induced tree.

α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αhcyc:¬G.IsAcyclicv:αc:G.Walk v vhc:c.IsCyclehc_length:G.girth = c.lengthp:G.Walk c.snd c.tail.penultimate := c.tail.dropLasts:Finset α := p.support.toFinseththree:3 ≤ G.girthhc_tail_path:c.tail.IsPathhp_path:p.IsPathhp_length:p.length = G.girth - 2hs_card:s.card = G.girth - 1hp_tree:(induce (↑s) G).IsTree⊢ G.girth - 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αhcyc:¬G.IsAcyclicv:αc:G.Walk v vhc:c.IsCyclehc_length:G.girth = c.lengthp:G.Walk c.snd c.tail.penultimate := c.tail.dropLasts:Finset α := p.support.toFinseththree:3 ≤ G.girthhc_tail_path:c.tail.IsPathhp_path:p.IsPathhp_length:p.length = G.girth - 2hs_card:s.card = G.girth - 1hp_tree:(induce (↑s) G).IsTreehbound:s.card ≤ G.largestInducedTreeSize⊢ G.girth - 1 ≤ G.largestInducedTreeSize All goals completed! 🐙omit [Fintype α] in

Every pair of vertices in a connected graph lies in an induced tree.

lemma Connected.exists_induced_tree_containing_pair {G : SimpleGraph α} (hG : G.Connected) (x y : α) : ∃ s : Finset α, x ∈ s ∧ y ∈ s ∧ (G.induce (s : Set α)).IsTree := α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:α⊢ ∃ s, x ∈ s ∧ y ∈ s ∧ (induce (↑s) G).IsTree α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ ∃ s, x ∈ s ∧ y ∈ s ∧ (induce (↑s) G).IsTree α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ x ∈ p.support.toFinsetα:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ y ∈ p.support.toFinsetα:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ (induce (↑p.support.toFinset) G).IsTree α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ x ∈ p.support.toFinset All goals completed! 🐙 α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ y ∈ p.support.toFinset All goals completed! 🐙 α:Type u_1inst✝:DecidableEq αG:SimpleGraph αhG:G.Connectedx:αy:αp:G.Walk x yleft✝:p.IsPathhp:p.length = G.dist x y⊢ (induce (↑p.support.toFinset) G).IsTree All goals completed! 🐙omit [DecidableEq α] in

A nonempty family of induced trees with prescribed vertices has a largest member.

α:Type u_1inst✝:Fintype αG:SimpleGraph αr:Finset αhr:∃ s, r ⊆ s ∧ (induce (↑s) G).IsTreeA:Set (Finset α) := {s | r ⊆ s ∧ (induce (↑s) G).IsTree}hAfin:A.FinitehAne:A.Nonempty⊢ ∃ s, r ⊆ s ∧ (induce (↑s) G).IsTree ∧ ∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.card α:Type u_1inst✝:Fintype αG:SimpleGraph αr:Finset αhr:∃ s, r ⊆ s ∧ (induce (↑s) G).IsTreeA:Set (Finset α) := {s | r ⊆ s ∧ (induce (↑s) G).IsTree}hAfin:A.FinitehAne:A.Nonemptys:Finset αhsA:s ∈ Ahmax:∀ b ∈ A, b.card ≤ s.card⊢ ∃ s, r ⊆ s ∧ (induce (↑s) G).IsTree ∧ ∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.card α:Type u_1inst✝:Fintype αG:SimpleGraph αr:Finset αhr:∃ s, r ⊆ s ∧ (induce (↑s) G).IsTreeA:Set (Finset α) := {s | r ⊆ s ∧ (induce (↑s) G).IsTree}hAfin:A.FinitehAne:A.Nonemptys:Finset αhsA:r ⊆ s ∧ (induce (↑s) G).IsTreehmax:∀ (b : Finset α), r ⊆ b ∧ (induce (↑b) G).IsTree → b.card ≤ s.card⊢ ∃ s, r ⊆ s ∧ (induce (↑s) G).IsTree ∧ ∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.card α:Type u_1inst✝:Fintype αG:SimpleGraph αr:Finset αhr:∃ s, r ⊆ s ∧ (induce (↑s) G).IsTreeA:Set (Finset α) := {s | r ⊆ s ∧ (induce (↑s) G).IsTree}hAfin:A.FinitehAne:A.Nonemptys:Finset αhsA:r ⊆ s ∧ (induce (↑s) G).IsTreehmax:∀ (b : Finset α), r ⊆ b ∧ (induce (↑b) G).IsTree → b.card ≤ s.card⊢ ∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.card α:Type u_1inst✝:Fintype αG:SimpleGraph αr:Finset αhr:∃ s, r ⊆ s ∧ (induce (↑s) G).IsTreeA:Set (Finset α) := {s | r ⊆ s ∧ (induce (↑s) G).IsTree}hAfin:A.FinitehAne:A.Nonemptys:Finset αhsA:r ⊆ s ∧ (induce (↑s) G).IsTreehmax:∀ (b : Finset α), r ⊆ b ∧ (induce (↑b) G).IsTree → b.card ≤ s.cardt:Finset αhrt:r ⊆ thT:(induce (↑t) G).IsTree⊢ t.card ≤ s.card All goals completed! 🐙

A nonempty proper vertex set in a connected graph has an edge across its boundary.

α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αhG:G.Connecteds:Finset αhsu:s ≠ Finset.univu:αhu:u ∈ sz:αhz:z ∉ sp:G.Walk u zd:G.Dartleft✝:d ∈ p.dartshd_in:d.toProd.1 ∈ ↑shd_out:d.toProd.2 ∉ ↑s⊢ ∃ z ∉ s, ∃ a ∈ s, G.Adj z a exact ⟨d.snd, α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αhG:G.Connecteds:Finset αhsu:s ≠ Finset.univu:αhu:u ∈ sz:αhz:z ∉ sp:G.Walk u zd:G.Dartleft✝:d ∈ p.dartshd_in:d.toProd.1 ∈ ↑shd_out:d.toProd.2 ∉ ↑s⊢ d.toProd.2 ∉ s All goals completed! 🐙, d.fst, α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αhG:G.Connecteds:Finset αhsu:s ≠ Finset.univu:αhu:u ∈ sz:αhz:z ∉ sp:G.Walk u zd:G.Dartleft✝:d ∈ p.dartshd_in:d.toProd.1 ∈ ↑shd_out:d.toProd.2 ∉ ↑s⊢ d.toProd.1 ∈ s All goals completed! 🐙, d.adj.symm⟩

A boundary vertex of a largest prescribed induced tree has two neighbors in the tree.

α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αr:Finset αs:Finset αhG:G.Connectedhrs:r ⊆ shs:s.NonemptyhT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ shza:G.Adj z ahex:¬∃ b ∈ s, b ≠ a ∧ G.Adj z bhuniq:∀ ⦃b : α⦄, b ∈ s → G.Adj z b → b = ahT':(induce (↑(insert z s)) G).IsTreehrs':r ⊆ insert z s⊢ ∃ z ∉ s, ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ G.Adj z a ∧ G.Adj z b α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αr:Finset αs:Finset αhG:G.Connectedhrs:r ⊆ shs:s.NonemptyhT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ shza:G.Adj z ahex:¬∃ b ∈ s, b ≠ a ∧ G.Adj z bhuniq:∀ ⦃b : α⦄, b ∈ s → G.Adj z b → b = ahT':(induce (↑(insert z s)) G).IsTreehrs':r ⊆ insert z shle:(insert z s).card ≤ s.card⊢ ∃ z ∉ s, ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ G.Adj z a ∧ G.Adj z b α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αr:Finset αs:Finset αhG:G.Connectedhrs:r ⊆ shs:s.NonemptyhT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), r ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ shza:G.Adj z ahex:¬∃ b ∈ s, b ≠ a ∧ G.Adj z bhuniq:∀ ⦃b : α⦄, b ∈ s → G.Adj z b → b = ahT':(induce (↑(insert z s)) G).IsTreehrs':r ⊆ insert z shle:(insert z s).card ≤ s.cardhcard:(insert z s).card = s.card + 1⊢ ∃ z ∉ s, ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ G.Adj z a ∧ G.Adj z b All goals completed! 🐙

Two leaves outside the boundary cycle force an extra two vertices in the induced tree.

α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjs:Finset αhT:(induce (↑s) G).IsTreex:αy:αz:αa:αb:αhxs:x ∈ shys:y ∈ shxy:x ≠ yhx:G.degree x = 1hy:G.degree y = 1hz:z ∉ sha:a ∈ shb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z be:induce (↑s) G ↪g G := Embedding.induce ↑sp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathright✝:∀ (y : (induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩), (fun p ↦ p.IsPath) y → y = pq:G.Walk a b := Walk.map e.toHom phq:q.IsPathhq_s:∀ w ∈ q.support, w ∈ shzq:z ∉ q.supportr:G.Walk a z := q.concat ⋯hr:r.IsPathhclose:s(z, a) ∉ r.edgesc:G.Walk z z := Walk.cons hza rhc:c.IsCyclehsubx:(G.neighborSet x).Subsingletonhsuby:(G.neighborSet y).Subsingletonhxz:x ≠ zhyz:y ≠ zhxnot:x ∉ c.supporthynot:y ∉ c.supporthqC:∀ ⦃w : α⦄, w ∈ q.support → w ∈ c.supporthqsub:q.support.toFinset ⊆ (s.erase x).erase yhqcard:q.support.toFinset.card = q.length + 1hy_erase:y ∈ s.erase xhcard:q.length + 1 ≤ s.card - 1 - 1hclen:c.length = q.length + 2⊢ G.girth + 1 ≤ s.card α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjs:Finset αhT:(induce (↑s) G).IsTreex:αy:αz:αa:αb:αhxs:x ∈ shys:y ∈ shxy:x ≠ yhx:G.degree x = 1hy:G.degree y = 1hz:z ∉ sha:a ∈ shb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z be:induce (↑s) G ↪g G := Embedding.induce ↑sp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathright✝:∀ (y : (induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩), (fun p ↦ p.IsPath) y → y = pq:G.Walk a b := Walk.map e.toHom phq:q.IsPathhq_s:∀ w ∈ q.support, w ∈ shzq:z ∉ q.supportr:G.Walk a z := q.concat ⋯hr:r.IsPathhclose:s(z, a) ∉ r.edgesc:G.Walk z z := Walk.cons hza rhc:c.IsCyclehsubx:(G.neighborSet x).Subsingletonhsuby:(G.neighborSet y).Subsingletonhxz:x ≠ zhyz:y ≠ zhxnot:x ∉ c.supporthynot:y ∉ c.supporthqC:∀ ⦃w : α⦄, w ∈ q.support → w ∈ c.supporthqsub:q.support.toFinset ⊆ (s.erase x).erase yhqcard:q.support.toFinset.card = q.length + 1hy_erase:y ∈ s.erase xhcard:q.length + 1 ≤ s.card - 1 - 1hclen:c.length = q.length + 2hg:G.girth ≤ c.length⊢ G.girth + 1 ≤ s.card All goals completed! 🐙

Two distinct leaves in a connected cyclic graph yield an induced tree of order at least girth plus one.

α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjhG:G.Connectedhcyc:¬G.IsAcyclicx:αy:αhxy:x ≠ yhx:G.degree x = 1hy:G.degree y = 1t:Finset αhxt:x ∈ thyt:y ∈ thTt:(induce (↑t) G).IsTreehr:∃ u, {x, y} ⊆ u ∧ (induce (↑u) G).IsTrees:Finset αhrs:{x, y} ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), {x, y} ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhxs:x ∈ shys:y ∈ shs:s.Nonemptyhsu:s ≠ Finset.univ⊢ G.girth + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjhG:G.Connectedhcyc:¬G.IsAcyclicx:αy:αhxy:x ≠ yhx:G.degree x = 1hy:G.degree y = 1t:Finset αhxt:x ∈ thyt:y ∈ thTt:(induce (↑t) G).IsTreehr:∃ u, {x, y} ⊆ u ∧ (induce (↑u) G).IsTrees:Finset αhrs:{x, y} ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), {x, y} ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhxs:x ∈ shys:y ∈ shs:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z b⊢ G.girth + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjhG:G.Connectedhcyc:¬G.IsAcyclicx:αy:αhxy:x ≠ yhx:G.degree x = 1hy:G.degree y = 1t:Finset αhxt:x ∈ thyt:y ∈ thTt:(induce (↑t) G).IsTreehr:∃ u, {x, y} ⊆ u ∧ (induce (↑u) G).IsTrees:Finset αhrs:{x, y} ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), {x, y} ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhxs:x ∈ shys:y ∈ shs:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bhbound:G.girth + 1 ≤ s.card⊢ G.girth + 1 ≤ G.largestInducedTreeSize All goals completed! 🐙end SimpleGraph