Definition: Trees and Forests 

Let \(G(V,E,\gamma)\) be an undirected graph.

• \(G\) is called a forest, if it contains only acyclic components.
• \(G\) is called a tree, if it has only one acyclic component.

| | | | | created: 2014-02-20 21:55:52 | modified: 2017-01-19 10:26:20 | by: bookofproofs | references: [570]

1.Proposition: Equivalent Definitions of Trees 

2.Definition: Root, Degree of a Tree, Subtree, Height 

3.Lemma: Lower Bound of Leaves in a Tree 

4.Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree 

5.Definition: Spanning Tree 

6.Definition: Graph Decomposable Into \(k\) Trees