/- Copyright 2026 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 FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.LargestInducedTree@[expose] public section

Induced trees, neighbourhood independence, and girth

Supporting API for WOWII (Graffiti.pc) Conjecture 141. Main results:

    SimpleGraph.indepNeighborsCard_add_one_le_largestInducedTreeSize: an independent set in a neighbourhood plus its centre induces a star, so indepNeighborsCard G v + 1 ≤ largestInducedTreeSize G.

    SimpleGraph.isIndepSet_neighborSet_of_four_le_girth: girth at least four makes every neighbourhood independent.

    SimpleGraph.maxDegree_add_girth_le_largestInducedTreeSize_add_three: for a connected cyclic graph of girth at least four, Δ(G) + girth(G) ≤ largestInducedTreeSize G + 3 — a maximum-order induced tree containing the closed neighbourhood of a maximum-degree vertex admits an outside vertex with two neighbours on the tree; the tree path joining them closes a cycle (so has length at least girth - 2) and shares at most three vertices with the closed neighbourhood.

namespace SimpleGraphsection PathHelpersvariable {β : Type*} {H : SimpleGraph β}

In a path, at most one edge is incident to the first vertex.

All goals completed! 🐙

In a path, at most two edges are incident to any fixed vertex w: among any three vertices joined to w by edges of the path, two coincide.

β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = chu₂:u₂ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = chu₂:u₂ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edgeshu₃:u₃ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edgeshu₃:u₃ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgeshu₁:u₁ = xhwc:w = cm₂:s(w, u₂) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βy:βhwx:¬w = xhu₁:u₁ = xh:H.Adj x wq:H.Walk w yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeskey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = w ∨ s(w, u) ∈ q.edgesm₂:s(w, u₂) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = chu₃:u₃ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = cm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = chu₃:u₃ = x⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgeshu₂:u₂ = xhwc:w = cm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βy:βhwx:¬w = xhu₂:u₂ = xh:H.Adj x wq:H.Walk w yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeskey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = w ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edgeshwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edgeshwc:w = c⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βy:βhwx:¬w = xh:H.Adj x wq:H.Walk w yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeskey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = w ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙 β:Type u_1H:SimpleGraph βa:βb:βw:βu₁:βu₂:βu₃:βx:βc:βy:βh:H.Adj x cq:H.Walk c yih:q.IsPath → s(w, u₁) ∈ q.edges → s(w, u₂) ∈ q.edges → s(w, u₃) ∈ q.edges → u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃hp:q.IsPath ∧ x ∉ q.supporth₁:s(w, u₁) ∈ (Walk.cons h q).edgesh₂:s(w, u₂) ∈ (Walk.cons h q).edgesh₃:s(w, u₃) ∈ (Walk.cons h q).edgeshwx:¬w = xkey:∀ (u : β), s(w, u) ∈ (Walk.cons h q).edges → u = x ∧ w = c ∨ s(w, u) ∈ q.edgesm₁:s(w, u₁) ∈ q.edgesm₂:s(w, u₂) ∈ q.edgesm₃:s(w, u₃) ∈ q.edges⊢ u₁ = u₂ ∨ u₁ = u₃ ∨ u₂ = u₃ All goals completed! 🐙

A path visiting a and b contains a subpath between a and b (in one of the two directions) whose support and edges lie in the original path.

β:Type u_1H:SimpleGraph βx:βy:βa:βb:βp:H.Walk x yhp:p.IsPathha:a ∈ p.supporthb:b ∈ p.supporthbt:b ∉ (p.takeUntil a ha).supporthbd:b ∈ (p.dropUntil a ha).support⊢ (∃ q, q.IsPath ∧ q.support ⊆ p.support ∧ q.edges ⊆ p.edges) ∨ ∃ q, q.IsPath ∧ q.support ⊆ p.support ∧ q.edges ⊆ p.edges All goals completed! 🐙

In a tree, the unique path between two adjacent vertices is the single edge.

private lemma tree_isPath_eq_cons_nil (hH : H.IsTree) {a b : β} (hab : H.Adj a b) {q : H.Walk a b} (hq : q.IsPath) : q = Walk.cons hab Walk.nil := β:Type u_1H:SimpleGraph βhH:H.IsTreea:βb:βhab:H.Adj a bq:H.Walk a bhq:q.IsPath⊢ q = Walk.cons hab Walk.nil β:Type u_1H:SimpleGraph βhH:H.IsTreea:βb:βhab:H.Adj a bq:H.Walk a bhq:q.IsPathP:H.Walk a bhuniq:∀ (y : H.Walk a b), (fun p ↦ p.IsPath) y → y = P⊢ q = Walk.cons hab Walk.nil exact (huniq q hq).trans (huniq (Walk.cons hab Walk.nil) (Walk.IsPath.nil.cons (β:Type u_1H:SimpleGraph βhH:H.IsTreea:βb:βhab:H.Adj a bq:H.Walk a bhq:q.IsPathP:H.Walk a bhuniq:∀ (y : H.Walk a b), (fun p ↦ p.IsPath) y → y = P⊢ a ∉ Walk.nil.support All goals completed! 🐙))).symm

Two path-vertices adjacent (in a tree) to a common vertex v force v onto the path: the unique tree path between them is the two-edge path through v, and the subpath of p between them must be that path.

β:Type u_1H:SimpleGraph βhH:H.IsTreev:βa:βb:βx:βy:βhva:H.Adj v ahvb:H.Adj v bhab:a ≠ bp:H.Walk x yhp:p.IsPathhap:a ∈ p.supporthbp:b ∈ p.supportq:H.Walk b ahq:q.IsPathhqs:q.support ⊆ p.supporthr:(Walk.cons ⋯ (Walk.cons hva Walk.nil)).IsPathP:H.Walk b ahuniq:∀ (y : H.Walk b a), (fun p ↦ p.IsPath) y → y = Pheq:q = Walk.cons ⋯ (Walk.cons hva Walk.nil)⊢ v ∈ (Walk.cons ⋯ (Walk.cons hva Walk.nil)).support All goals completed! 🐙

If v lies on a path in a tree and a is a path-vertex adjacent to v, then the edge s(v, a) is an edge of the path: the subpath of p between v and a is the unique tree path, which is the single edge.

β:Type u_1H:SimpleGraph βhH:H.IsTreev:βa:βx:βy:βhva:H.Adj v ap:H.Walk x yhp:p.IsPathhvp:v ∈ p.supporthap:a ∈ p.supportq:H.Walk a vhq:q.IsPathhqe:q.edges ⊆ p.edgesheq:q = Walk.cons ⋯ Walk.nilhmem:s(a, v) ∈ p.edges⊢ s(v, a) ∈ p.edges rwa [β:Type u_1H:SimpleGraph βhH:H.IsTreev:βa:βx:βy:βhva:H.Adj v ap:H.Walk x yhp:p.IsPathhvp:v ∈ p.supporthap:a ∈ p.supportq:H.Walk a vhq:q.IsPathhqe:q.edges ⊆ p.edgesheq:q = Walk.cons ⋯ Walk.nilhmem:s(v, a) ∈ p.edges⊢ s(v, a) ∈ p.edgesβ:Type u_1H:SimpleGraph βhH:H.IsTreev:βa:βx:βy:βhva:H.Adj v ap:H.Walk x yhp:p.IsPathhvp:v ∈ p.supporthap:a ∈ p.supportq:H.Walk a vhq:q.IsPathhqe:q.edges ⊆ p.edgesheq:q = Walk.cons ⋯ Walk.nilhmem:s(v, a) ∈ p.edges⊢ s(v, a) ∈ p.edges at hmemend PathHelperssection TreePathvariable {α : Type*} {G : SimpleGraph α}

Mapping a path of an induced tree into G and closing it up through an outside vertex z adjacent to both endpoints produces a cycle of length p.length + 2, so the girth is at most p.length + 2.

α:Type u_1G:SimpleGraph αs:Finset α_hT:(induce (↑s) G).IsTreez:αa:αb:αhz:z ∉ sha:a ∈ shb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathe:induce (↑s) G ↪g G := Embedding.induce ↑sq:G.Walk a b := Walk.map e.toHom phq:q.IsPathhq_length:q.length = p.lengthhq_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.IsCyclehclen:c.length = q.length + 2⊢ G.girth ≤ p.length + 2 α:Type u_1G:SimpleGraph αs:Finset α_hT:(induce (↑s) G).IsTreez:αa:αb:αhz:z ∉ sha:a ∈ shb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathe:induce (↑s) G ↪g G := Embedding.induce ↑sq:G.Walk a b := Walk.map e.toHom phq:q.IsPathhq_length:q.length = p.lengthhq_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.IsCyclehclen:c.length = q.length + 2hg:G.girth ≤ c.length⊢ G.girth ≤ p.length + 2 All goals completed! 🐙

Triangle-free bridge: in a graph of girth at least 4, the neighborhood of any vertex is an independent set. An edge inside a neighborhood would close a 3-cycle with the two star edges.

α:Type u_1G:SimpleGraph αhg4:4 ≤ G.girthv:αx:αhx:x ∈ G.neighborSet vy:αhy:y ∈ G.neighborSet va✝:x ≠ yhadj:G.Adj x yhvx:G.Adj v xhvy:G.Adj v yhxv:x ≠ vhr:(Walk.cons hadj (Walk.cons ⋯ Walk.nil)).IsPathhclose:s(v, x) ∉ (Walk.cons hadj (Walk.cons ⋯ Walk.nil)).edgeshc:(Walk.cons hvx (Walk.cons hadj (Walk.cons ⋯ Walk.nil))).IsCyclehg:G.girth ≤ 3⊢ False All goals completed! 🐙end TreePathsection Mainvariable {α : Type*} [Fintype α] [DecidableEq α] {G : SimpleGraph α}

Overlap lemma: on a path p in an induced tree on s, at most 3 vertices lie in the closed neighborhood of a fixed vertex v ∈ s. Here the path support is read off in α via Subtype.val.

α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjs:Finset αhT:(induce (↑s) G).IsTreev:αhv:v ∈ sx:↑↑sy:↑↑sp:(induce (↑s) G).Walk x yhp:p.IsPathhvs:v ∈ ↑sW:Finset α := (List.map Subtype.val p.support).toFinsethW:W = (List.map Subtype.val p.support).toFinsethmemW:∀ (u : α), u ∈ W ↔ ∃ û ∈ p.support, ↑û = uhadj_of_mem:∀ (û : ↑↑s) (u : α), ↑û = u → u ∈ G.neighborFinset v → (induce (↑s) G).Adj ⟨v, hvs⟩ ûhinter:(W ∩ G.neighborFinset v).card ≤ 2hsub:W ∩ insert v (G.neighborFinset v) ⊆ insert v (W ∩ G.neighborFinset v)⊢ (W ∩ insert v (G.neighborFinset v)).card ≤ 3 calc (W ∩ insert v (G.neighborFinset v)).card ≤ (insert v (W ∩ G.neighborFinset v)).card := Finset.card_le_card hsub _ ≤ (W ∩ G.neighborFinset v).card + 1 := Finset.card_insert_le _ _ _ ≤ 3 := α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjs:Finset αhT:(induce (↑s) G).IsTreev:αhv:v ∈ sx:↑↑sy:↑↑sp:(induce (↑s) G).Walk x yhp:p.IsPathhvs:v ∈ ↑sW:Finset α := (List.map Subtype.val p.support).toFinsethW:W = (List.map Subtype.val p.support).toFinsethmemW:∀ (u : α), u ∈ W ↔ ∃ û ∈ p.support, ↑û = uhadj_of_mem:∀ (û : ↑↑s) (u : α), ↑û = u → u ∈ G.neighborFinset v → (induce (↑s) G).Adj ⟨v, hvs⟩ ûhinter:(W ∩ G.neighborFinset v).card ≤ 2hsub:W ∩ insert v (G.neighborFinset v) ⊆ insert v (W ∩ G.neighborFinset v)⊢ (W ∩ G.neighborFinset v).card + 1 ≤ 3 All goals completed! 🐙omit [Fintype α] in

Extract an explicit independent neighbour set witnessing indepNeighborsCard.

α:Type u_1inst✝:DecidableEq αG:SimpleGraph αv:αs:Finset ↑(G.neighborSet v)hs:(induce (G.neighborSet v) G).IsNIndepSet (induce (G.neighborSet v) G).indepNum s⊢ s.card = G.indepNeighborsCard v All goals completed! 🐙omit [Fintype α] in

A vertex together with an independent set of its neighbours induces a star, hence a tree.

α:Type u_1inst✝:DecidableEq αG:SimpleGraph αv:αs:αS₀:Finset αhs:s ∉ S₀ih:(∀ s ∈ S₀, G.Adj v s) → G.IsIndepSet ↑S₀ → (induce (↑(insert v S₀)) G).IsTreehadj:∀ s_1 ∈ insert s S₀, G.Adj v s_1hind:G.IsIndepSet ↑(insert s S₀)hadj₀:∀ x ∈ S₀, G.Adj v xhind₀:G.IsIndepSet ↑S₀hT:(induce (↑(insert v S₀)) G).IsTreehsv:s ≠ vhzs:s ∉ insert v S₀hza:G.Adj s vhuniq:∀ ⦃b : α⦄, b ∈ insert v S₀ → G.Adj s b → b = vhT':(induce (↑(insert s (insert v S₀))) G).IsTreehcomm:insert v (insert s S₀) = insert s (insert v S₀)⊢ (induce (↑(insert s (insert v S₀))) G).IsTree All goals completed! 🐙

The star bound: indepNeighborsCard G v + 1 ≤ largestInducedTreeSize G.

lemma indepNeighborsCard_add_one_le_largestInducedTreeSize (G : SimpleGraph α) (v : α) : indepNeighborsCard G v + 1 ≤ largestInducedTreeSize G := α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:α⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize classical α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard v⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ S⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ ShT:(induce (↑(insert v S)) G).IsTree⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ ShT:(induce (↑(insert v S)) G).IsTreehbound:(insert v S).card ≤ G.largestInducedTreeSize⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize rwa [α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ ShT:(induce (↑(insert v S)) G).IsTreehbound:S.card + 1 ≤ G.largestInducedTreeSize⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ ShT:(induce (↑(insert v S)) G).IsTreehbound:G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSizeα:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:αS:Finset αhadj:∀ s ∈ S, G.Adj v shind:G.IsIndepSet ↑Shcard:S.card = G.indepNeighborsCard vhvS:v ∉ ShT:(induce (↑(insert v S)) G).IsTreehbound:G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize⊢ G.indepNeighborsCard v + 1 ≤ G.largestInducedTreeSize at hboundomit [DecidableEq α] in

The independence number of a neighbourhood is at most the degree.

All goals completed! 🐙

Main counting theorem: in a connected graph with a cycle and girth at least 4, Δ(G) + girth(G) ≤ largestInducedTreeSize G + 3.

Proof: grow a maximum induced tree s through the closed neighborhood of a maximum-degree vertex v; a boundary vertex z of s has two neighbors a ≠ b in s, and the tree path from a to b closes through z into a cycle, so it has at least girth − 2 edges; the path meets the closed neighborhood of v in at most 3 vertices, so inclusion–exclusion inside s gives the bound.

α:Type u_1inst✝³:Fintype αinst✝²:DecidableEq αG:SimpleGraph αinst✝¹:DecidableRel G.Adjinst✝:Nontrivial αhG:G.Connectedhcyc:¬G.IsAcyclichg4:4 ≤ G.girthv:αhvdeg:G.maxDegree = G.degree vhadjS:∀ u ∈ G.neighborFinset v, G.Adj v uhind:G.IsIndepSet ↑(G.neighborFinset v)hT0:(induce (↑(insert v (G.neighborFinset v))) G).IsTrees:Finset αhrs:insert v (G.neighborFinset v) ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), insert v (G.neighborFinset v) ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhvs:v ∈ shsne:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathhgirth:G.girth ≤ p.length + 2hoverlap:((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card ≤ 3hWcard:(List.map Subtype.val p.support).toFinset.card = p.length + 1hr0card:(insert v (G.neighborFinset v)).card = G.maxDegree + 1hWsub:(List.map Subtype.val p.support).toFinset ⊆ s⊢ G.maxDegree + G.girth ≤ G.largestInducedTreeSize + 3 α:Type u_1inst✝³:Fintype αinst✝²:DecidableEq αG:SimpleGraph αinst✝¹:DecidableRel G.Adjinst✝:Nontrivial αhG:G.Connectedhcyc:¬G.IsAcyclichg4:4 ≤ G.girthv:αhvdeg:G.maxDegree = G.degree vhadjS:∀ u ∈ G.neighborFinset v, G.Adj v uhind:G.IsIndepSet ↑(G.neighborFinset v)hT0:(induce (↑(insert v (G.neighborFinset v))) G).IsTrees:Finset αhrs:insert v (G.neighborFinset v) ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), insert v (G.neighborFinset v) ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhvs:v ∈ shsne:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathhgirth:G.girth ≤ p.length + 2hoverlap:((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card ≤ 3hWcard:(List.map Subtype.val p.support).toFinset.card = p.length + 1hr0card:(insert v (G.neighborFinset v)).card = G.maxDegree + 1hWsub:(List.map Subtype.val p.support).toFinset ⊆ shie:((List.map Subtype.val p.support).toFinset ∪ insert v (G.neighborFinset v)).card + ((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card = (List.map Subtype.val p.support).toFinset.card + (insert v (G.neighborFinset v)).card⊢ G.maxDegree + G.girth ≤ G.largestInducedTreeSize + 3 α:Type u_1inst✝³:Fintype αinst✝²:DecidableEq αG:SimpleGraph αinst✝¹:DecidableRel G.Adjinst✝:Nontrivial αhG:G.Connectedhcyc:¬G.IsAcyclichg4:4 ≤ G.girthv:αhvdeg:G.maxDegree = G.degree vhadjS:∀ u ∈ G.neighborFinset v, G.Adj v uhind:G.IsIndepSet ↑(G.neighborFinset v)hT0:(induce (↑(insert v (G.neighborFinset v))) G).IsTrees:Finset αhrs:insert v (G.neighborFinset v) ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), insert v (G.neighborFinset v) ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhvs:v ∈ shsne:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathhgirth:G.girth ≤ p.length + 2hoverlap:((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card ≤ 3hWcard:(List.map Subtype.val p.support).toFinset.card = p.length + 1hr0card:(insert v (G.neighborFinset v)).card = G.maxDegree + 1hWsub:(List.map Subtype.val p.support).toFinset ⊆ shie:((List.map Subtype.val p.support).toFinset ∪ insert v (G.neighborFinset v)).card + ((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card = (List.map Subtype.val p.support).toFinset.card + (insert v (G.neighborFinset v)).cardhle:((List.map Subtype.val p.support).toFinset ∪ insert v (G.neighborFinset v)).card ≤ s.card⊢ G.maxDegree + G.girth ≤ G.largestInducedTreeSize + 3 α:Type u_1inst✝³:Fintype αinst✝²:DecidableEq αG:SimpleGraph αinst✝¹:DecidableRel G.Adjinst✝:Nontrivial αhG:G.Connectedhcyc:¬G.IsAcyclichg4:4 ≤ G.girthv:αhvdeg:G.maxDegree = G.degree vhadjS:∀ u ∈ G.neighborFinset v, G.Adj v uhind:G.IsIndepSet ↑(G.neighborFinset v)hT0:(induce (↑(insert v (G.neighborFinset v))) G).IsTrees:Finset αhrs:insert v (G.neighborFinset v) ⊆ shT:(induce (↑s) G).IsTreehmax:∀ (t : Finset α), insert v (G.neighborFinset v) ⊆ t → (induce (↑t) G).IsTree → t.card ≤ s.cardhvs:v ∈ shsne:s.Nonemptyhsu:s ≠ Finset.univz:αhz:z ∉ sa:αha:a ∈ sb:αhb:b ∈ shab:a ≠ bhza:G.Adj z ahzb:G.Adj z bp:(induce (↑s) G).Walk ⟨a, ⋯⟩ ⟨b, ⋯⟩hp:p.IsPathhgirth:G.girth ≤ p.length + 2hoverlap:((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card ≤ 3hWcard:(List.map Subtype.val p.support).toFinset.card = p.length + 1hr0card:(insert v (G.neighborFinset v)).card = G.maxDegree + 1hWsub:(List.map Subtype.val p.support).toFinset ⊆ shie:((List.map Subtype.val p.support).toFinset ∪ insert v (G.neighborFinset v)).card + ((List.map Subtype.val p.support).toFinset ∩ insert v (G.neighborFinset v)).card = (List.map Subtype.val p.support).toFinset.card + (insert v (G.neighborFinset v)).cardhle:((List.map Subtype.val p.support).toFinset ∪ insert v (G.neighborFinset v)).card ≤ s.cardhscard:s.card ≤ G.largestInducedTreeSize⊢ G.maxDegree + G.girth ≤ G.largestInducedTreeSize + 3 All goals completed! 🐙end Mainend SimpleGraph