Discrete Math › Section C · Graph theory › Topic C.2

Trees and their properties

A tree is the leanest way to hold a set of vertices together: connected, but with no edge to spare. That simple definition produces a remarkable list of facts, from an exact edge count to unique routes between vertices, and trees turn up everywhere from folder systems to sorting.

Connected, with no cycles

A tree is a connected graph that contains no cycles. A forest is a graph with no cycles, connected or not, so each component of a forest is a tree. A single path, a star with one centre joined to several outer vertices, and the folder structure on a computer are all trees. A cycle such as \(C_4\) is not, and two separate paths form a forest rather than a tree. Trees are the minimal connected graphs: every edge does necessary work.

Exactly one path between any two vertices

Trees are exactly the graphs in which every two distinct vertices are joined by one and only one path. Suppose a tree had two different paths from \(u\) to \(v\). Follow them from \(u\) to the first place they split, then on to the first later vertex where they meet again; the two stretches between those points form a cycle, which a tree cannot contain. Conversely, if a graph had a cycle, any two vertices on it would be joined both clockwise and anticlockwise around it. In a forest, any two vertices are joined by at most one path.

Every tree has leaves

A leaf is a vertex of degree 1, and any tree on two or more vertices has two or more leaves. To see why, take a longest path in the tree and look at one of its ends, \(u\). Any neighbour of \(u\) other than the next vertex on the path would either lie on the path, closing a cycle, or lie off it, giving a longer path. Neither is allowed, so \(u\) has degree 1, and so does the other end. Removing a leaf and its edge from a tree leaves a smaller tree.

A tree with n vertices has n − 1 edges

This is the most used fact about trees. Suppose it failed, and take a counterexample \(T\) with as few vertices as possible, say \(n\). A one-vertex tree has 0 edges, so \(n \ge 2\) and \(T\) has a leaf. Removing that leaf and its edge gives a tree with \(n - 1\) vertices, which is smaller than \(T\), so it obeys the rule and has \(n - 2\) edges. Then \(T\) has \(n - 1\) edges after all, a contradiction. It follows that a forest with \(n\) vertices and \(c\) components has \(n - c\) edges, since each component loses one.

Worked example: counting leaves

A tree has three vertices of degree 3, one vertex of degree 2, and every other vertex is a leaf. How many leaves are there? 1. Let \(L\) be the number of leaves, so there are \(n = 4 + L\) vertices. 2. A tree has \(n - 1 = 3 + L\) edges. 3. The degree sum is \(3 \cdot 3 + 2 + L = 11 + L\). 4. By the handshake lemma, \(11 + L = 2(3 + L) = 6 + 2L\), so \(L = 5\). 5. Check by building one: join \(a\) to \(b\), to \(c\) and to one leaf; give \(b\) two leaves; give \(c\) one leaf and a neighbour \(d\); give \(d\) one leaf. That tree has 9 vertices, 8 edges and 5 leaves.

Three properties, any two will do

For a graph with \(n\) vertices, consider three properties: it is connected, it has no cycles, and it has \(n - 1\) edges. Any two of them force the third, so any two prove the graph is a tree. Two more facts describe how tight a tree is. Deleting any edge of a tree disconnects it, because that edge was the only path between its ends. Adding any new edge between two existing vertices creates exactly one cycle: the new edge plus the unique path that already joined its ends.

Rooted trees

Choosing one vertex as the root turns a tree into a rooted tree, usually drawn with the root at the top. Each other vertex has a parent, the next vertex on its unique path towards the root, and the vertices below a vertex are its children. Ancestors and descendants extend these ideas up and down the tree. In a rooted tree a leaf means a vertex with no children. The depth of a vertex is the length of its path to the root, so the root has depth 0, and the height of the tree is the greatest depth.

Binary trees

A binary tree is a rooted tree in which each vertex has at most two children, each labelled left or right. Depth \(d\) holds at most \(2^d\) vertices, so a binary tree of height \(h\) has at most

1 + 2 + 4 + \cdots + 2^h = 2^{h+1} - 1

vertices. Turned around, storing \(n\) items needs height at least about \(\log_2 n\). A million items need height at least 19, since \(2^{20} - 1 = 1,048,575\) is enough and \(2^{19} - 1 = 524,287\) is not. That logarithmic height is why tree-shaped data can be searched quickly.

Worked example: three traversals

A traversal visits every vertex of a rooted tree in a fixed order. Take a binary tree with root 8, whose left child is 3 and right child is 10; 3 has left child 1 and right child 6, and 10 has only a right child, 14. 1. Preorder (vertex, then left subtree, then right subtree): 8, 3, 1, 6, 10, 14. 2. Inorder (left subtree, vertex, right subtree): 1, 3, 6, 8, 10, 14. 3. Postorder (left, right, then vertex): 1, 6, 3, 14, 10, 8. The inorder list is sorted because this is a binary search tree: everything in a vertex's left subtree is smaller than it and everything in its right subtree is larger.

How many trees are there?

Count the different trees on a fixed set of \(n\) labelled vertices. Cayley's formula says there are \(n^{n-2}\) of them. Check \(n = 3\): a tree on 3 vertices is a path, determined by which vertex is in the middle, so there are 3, and \(3^1 = 3\). Check \(n = 4\): a tree is either a star, with 4 choices of centre, or a path, with \(4!/2 = 12\) orderings (each path read in two directions), giving 16, and \(4^2 = 16\). Unlabelled shapes are far fewer: just 2 on four vertices. Binary tree shapes with \(n\) vertices are counted by the Catalan numbers 1, 2, 5, 14, ... for \(n = 1, 2, 3, 4\).

Common mistakes to avoid

First, calling any graph with \(n - 1\) edges a tree: it must also be connected or acyclic, since a triangle plus a separate vertex has 4 vertices and 3 edges. Second, forgetting that a forest with \(c\) components has \(n - c\) edges, not \(n - 1\). Third, mixing up the two meanings of leaf: degree 1 in a tree, no children in a rooted tree, where the root itself may have degree 1. Fourth, mixing up traversal orders; say the rule aloud (left, vertex, right for inorder) before listing.

Key takeaways

A tree is connected and has no cycles; equivalently, exactly one path joins any two vertices. Every tree with two or more vertices has at least two leaves, and a tree with \(n\) vertices has \(n - 1\) edges. Any two of connected, acyclic and \(n - 1\) edges imply the third. Rooted trees add parents, children, depth and height; a binary tree of height \(h\) has at most \(2^{h+1} - 1\) vertices. Preorder, inorder and postorder are the three standard traversals, and there are \(n^{n-2}\) labelled trees on \(n\) vertices.

Flashcards

Flashcard

Tree

A connected graph with no cycles

The minimal connected graphs.

Test your understanding

Question 1 of 5

How many edges does a tree with 40 vertices have?

Question 2 of 5

A forest has 30 vertices and 4 components. How many edges does it have?

Question 3 of 5

A tree has two vertices of degree 4, one vertex of degree 3, and all other vertices are leaves. How many leaves does it have?

Question 4 of 5

A binary tree has root 5. Its left child is 2, whose children are 1 (left) and 4 (right); its right child is 9, a leaf. What is the postorder traversal?

Question 5 of 5

A connected graph has 12 vertices and 11 edges. What can you conclude?

← Previous topicNext topic →