Graph theory · Definition
Tree
Before you start you need to know
It is the minimal structure that keeps all vertices connected; it appears in hierarchies, networks and search algorithms.
Definition
A tree \(T=(V,E)\) is a connected graph that contains no cycles.
A tree with \(n\) vertices has exactly \(n-1\) edges. This is equivalent to the other characterizations: it is connected and acyclic; it is connected and removing any edge disconnects it; between each pair of vertices there is a unique simple path. Any of them can be taken as the definition and the rest become theorems.
Every tree with at least two vertices has at least two leaves, vertices of degree 1: the endpoints of a longest path are leaves. Removing a leaf leaves a smaller tree, which is why many proofs about trees go by induction on the number of vertices. An acyclic graph, not necessarily connected, is called a forest, and each of its components is a tree.
Guiding example: the path \(1,2,3,4,5\) is a tree with 5 vertices and 4 edges; adding the edge \(15\) creates a cycle and it stops being a tree. A typical mistake is to check only the number of edges: \(n-1\) edges are not enough, since a triangle plus an isolated vertex has 4 vertices and 3 edges but is not connected. Spanning trees and Cayley's formula, which counts \(n^{n-2}\) labeled trees, start from this idea.
Think about it
Is a graph with 5 vertices and 4 edges always a tree?
No: a triangle plus an edge between the other two vertices has 5 vertices and 4 edges, but it is not connected and has a cycle. It must also be connected or acyclic.
Exercises 10
- How many edges does a tree with 10 vertices have?
- A tree has 15 edges. How many vertices does it have?
- The vertices are \(1,\dots,5\). Which of these edge sets forms a tree?
- What is the sum of the vertex degrees of a tree with 7 vertices?
- A tree with 7 vertices has one vertex of degree 4, one of degree 3, and the rest are leaves (degree 1). How many leaves does it have?
- One edge is removed from a tree. How many connected components does the resulting graph have?
- How many different trees are there on labeled vertices \(1,2,3,4\)?
- An acyclic graph has 10 vertices and 3 connected components. How many edges must be added, without creating cycles, to make it a tree?
- An edge is added to a tree between two vertices that were not adjacent. The result:
- Which of the following statements is true for every tree?
References
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §11.1
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.5
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §12.1