Trees

22 March 2010


Introduction

A path in a tree is a sequence of distinct vertices v1,v2,...,vn such that vi is connected by an edge to vi+1 for i=1,2,...,n-1. A cycle, or a circuit, is a sequence of vertices v1,v2,...,vn such that v1,v2,...,vn-1 is a path, and v1=vn. In the graph below, a cycle is highlighted in red.

A graph is connected if every vertex can be joined to every other vertex by a path. The above graph is not connected, because the two yellow vertices cannot be joined to the others by a path.

A connected graph which has no cycles whatsoever is called a tree. There are several trees built in to Graph Constructor. To obtain them, click on the 'node' button, and a new button at the bottom labelled 'select graph' will appear. Click on 'select graph' and choose 'tree' from the popup menu. Another special type of tree that appears in the popup menu is 'star'. Take a look at these graphs too. Are there any more special types of tree in the popup list?

Investigation 1: tree counting

Let's count trees. How many trees are there with n vertices? In the previous section we explored all possible graphs with fewer than five vertices. Which of those are trees? There are two trees with four vertices, and they are shown below. How many trees are there with five vertices?

There are six trees with six vertices. Can you find them all? How do you know there are no more?

Investigation 2: edge counting

For each tree you have considered so far, count the number of edges, and count the number of vertices. What do you notice? If you see a relationship then can you prove that this relationship holds for all trees? It may help if you know about induction.

Let E be the number of edges of a tree, and let V be the number of vertices. The relationship described in the previous paragraph is E=V-1. How are E and V related for general connected graphs? Choose any connected graph. Choose an edge in that graph. Would the graph still be connected if you removed that edge? If yes, then remove it. If no, then move on to another edge and ask the same question again. Once you have asked that question of every single edge, and removed certain edges along the way, you will be left with a tree. What does this tell you about the relationship betwee E and V for general connected graphs?

Investigation 3: unique paths

Choose two vertices A and B of a tree. How many paths are there from A to B? In the tree below there is only one path from A to B, highlighted in red.

Can you find a tree with more than one path between two vertices? If not then why not?

Suppose, on the other hand, that we have a graph in which there is a unique path between every pair of vertices. Is the graph a tree?

Other topics

Another necessary and sufficient property for a connected graph to be a tree is that if you remove an edge it splits the tree in to two components.