Labeled Tree Basic
DefinitionAnalyticCombinatorics_Ch7_SingularityApp_LabeledTreeBasicanalytic-combinatoricslean4tree-models
The mathematical objects and operations are specified by the following source definitions.
def LabeledTree (n : ℕ) : Type :=
{G : SimpleGraph (Fin n) // G.IsTree}
def RootedLabeledTree (n : ℕ) : Type :=
LabeledTree n × Fin n
Definition code
import Mathlib
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Labelled trees on a finite vertex set
We introduce the genuine combinatorial object underlying Cayley's formula: the
type of labelled trees on `Fin n`, namely simple graphs on `Fin n` that are
trees (connected and acyclic), and the rooted version. These are finite types.
The cardinality results (`card (LabeledTree n) = n^(n-2)`,
`card (RootedLabeledTree n) = n^(n-1)`) and the connection to the banked
`cayleyRootedTree` are established in `Prufer.lean` / `Cayley.lean`.
-/
namespace AnalyticCombinatorics.Ch7.SingularityApp.LabeledTreeNS
/-- A labelled tree on `n` vertices: a simple graph on `Fin n` that is a tree. -/
def LabeledTree (n : ℕ) : Type :=
{G : SimpleGraph (Fin n) // G.IsTree}
/-- A rooted labelled tree on `n` vertices. -/
def RootedLabeledTree (n : ℕ) : Type :=
LabeledTree n × Fin n
instance instFiniteLabeledTree (n : ℕ) : Finite (LabeledTree n) := by
unfold LabeledTree; infer_instance
noncomputable instance instFintypeLabeledTree (n : ℕ) : Fintype (LabeledTree n) :=
Fintype.ofFinite _
noncomputable instance instFintypeRootedLabeledTree (n : ℕ) :
Fintype (RootedLabeledTree n) := by
unfold RootedLabeledTree; infer_instance
end AnalyticCombinatorics.Ch7.SingularityApp.LabeledTreeNS
Source