A finite forest with an edge has a vertex of degree one
ProvedArexychen.Erdos180.exists_degree_one_of_isAcyclic_of_edgearexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a simple graph on a finite vertex type, with decidable adjacency. If is acyclic and its finite edge set is nonempty, then some vertex has degree exactly one.
Preamble
import Mathlib.Analysis.Asymptotics.Theta import Mathlib.Combinatorics.SimpleGraph.Acyclic import Mathlib.Combinatorics.SimpleGraph.Basic import Mathlib.Combinatorics.SimpleGraph.DeleteEdges import Mathlib.Combinatorics.SimpleGraph.Finite import Mathlib.Combinatorics.SimpleGraph.Maps import Mathlib.Combinatorics.SimpleGraph.Matching import Mathlib.Combinatorics.SimpleGraph.Subgraph import Mathlib.Tactic open Filter open Asymptotics attribute [local instance] SimpleGraph.neighborSetFintype universe u v
Formal statement
theorem Arexychen.Erdos180.exists_degree_one_of_isAcyclic_of_edge
{α : Type u} [Fintype α] (F : SimpleGraph α) [DecidableRel F.Adj]
(hF : F.IsAcyclic) (hedge : F.edgeFinset.Nonempty) :
∃ v : α, F.degree v = 1 := by sorry
Source