A tree is a connected graph that has no circuits as subgraphs.
A graph that has no circuits as subgraphs but is not necessarily connected is a forest.
Java Web Start Activity:
In the Java Web Start application below you can draw examples of
trees for yourself.
In many situations we will choose one of the vertices of a tree to be special and call it the root of the tree. The graph is then called a rooted tree. Usually rooted trees are drawn in a treelike shape with the root at the top. A tree that is not a rooted tree is called a free tree.
Java Web Start Activity:
In the Java Web Start application below you can draw examples of
rooted trees for yourself. By choosing different vertices to be the
root you can make the application draw the tree differently.
In a rooted tree, the vertices adjacent to the root vertex are called its children. The children of the root are said to be on level 1. The root vertex is the parent vertex of the vertices on level 1. In the same way, if a vertex v is at level i, then the vertices other than the parent vertex of v that are adjacent to v are the children of v. The children of v are at level i+1 and v is their parent vertex. Note that the number of levels depends on which vertex is chosen to be the root. The number of levels is the height of the tree.
Vertices that have no children are called leaves. The vertices that are not leaves are said to be internal vertices. The root counts as an internal vertex.
If all the internal vertices of a tree have the same number, say n, of vertices then it is an nary tree. A nary tree with n=2 is called a binary tree. Figure 32.1 shows a binary tree with three levels. The leaves of the tree are vertices 8, 9, 5, 6, 10, 11.
 

If all the leaves of an nary tree are at the same level then it is a full nary tree.
Petersen Activity:
In the Petersen program select
Graph  Named Graph  Full nary Tree.
When asked for
n, input
2 and when asked for the number of levels input
3. You should get a graph that looks like figure
32.2.
 

Java Web Start Activity:
The Java Web Start application below will give you more examples of
full nary trees.

Use the Petersen program and, by looking at the statistics, find
the number of vertices and the number of edges in a full binary
tree with
 2 levels
 3 levels
 4 levels.
 Note that the number of vertices in a full binary tree with h levels is 1 + 2 + 2^{2} + 2^{3} + ... + 2^{h}. What is the sum of this series?
 How many leaves does a full binary tree with h levels have? How many leaves does a full binary tree with 25 levels have?
 How many internal vertices does a full binary tree with h levels have?
An nary tree with n = 3 is called a ternary tree. Figure 32.1 shows a full ternary tree with 3 levels.
 

 How many vertices will a full ternary tree with h levels have?
 How many leaves are there in
 a full ternary tree with 25 levels?
 a full nary tree with h levels?
 Note that in any rooted tree, every vertex has an edge joining it to its parent (except the root which has no parent). How many edges in total should a tree with n vertices have?
 Use the program to decide which of the trees in question 1) are bipartite.
 If a graph is a tree, what is its chromatic number.
 If an n x n matrix is the adjacency matrix of a tree, how many zeros and how many ones should it have?
 Prove that if a tree T_{1} is a subgraph of a tree T_{2} then T_{1} is an induced subgraph of T_{2}.
Answers
© C. Mawata