Graph Theory Lessons

1. 
   

   Levels	Number of vertices	Number of edges
   2	7	6
   3	15	14
   4	31	30

2. If you remember the formula for the sum of a finite geometric series then you can answer this question very quickly. The formula is worth remembering as if the more general one . It might be instructive to look at the problem another way so let S represent the sum. .
   Then
   So
   
   
   Can you prove the same result using induction?

3. A full binary tree with h levels has 2^h leaves. A full binary tree with 25 levels has 2²⁵ leaves.

4. From the results of the previous two questions, a full binary tree with h levels has internal vertices.

5. The number of vertices in a full ternary tree with h levels is
   Try to show using the method we used for the case of the binary tree that
   
   How many vertices will a full 4-ary tree with h levels have? In general a series of the form
   is called a geometric series. Can you find how many vertices a full n-ary tree with h levels has?

6. A full ternary tree with 25 levels has 3²⁵ leaves.
   A full n-ary tree with h levels has n^h leaves.

7. A tree with n vertices has n-1 edges. Note that it does not have to be a full tree.

8. All trees are bipartite.

9. All trees have chromatic number 2.

10. In an adjacency matrix A we have 1 in positions A_i,j and A_j,i if there is an edge from vertex i to vertex j. Since we have n - 1 edges the matrix must have 2n - 2 ones and n² - 2n + 2 zeros.

11. 
    

    Vertex	Breadth First	Depth First
    1	0	0
    2	1	1
    3	8	2
    4	2	3
    5	5	4
    6	9	5
    7	12	6
    8	3	7
    9	4	8
    10	6	9
    11	7	10
    12	10	11
    13	11	12
    14	13	13
    15	14	14

12. Vertices 1, 2,14,15 require the same number of steps when you do a breadth first search as when you do a depth first search.

13. In both cases the sum of the columns is
    
    
14. Here is another sum that you should always remember: If the tree has n vertices then the average number of steps is
    .

15. The last vertex on level 1 is vertex 4, the last one on level 2 is vertex 13, and in general the last vertex on level h is vertex
    
    Substituting h = 3 gives that the vertex 40 is the last vertex on level 3, and similarly the last vertex on level 4 is vertex 121. Therefore vertex 50 is on level 4.

    The children of vertex 41 are vertices 122, 123, and 124; those of vertex 42 are vertices 125, 126, 127. We can see that if vertex 41+ x is on level 4, its children are labeled 122 + 3x, 123 + 3x, and 124 + 3x. In particular the children of vertex 50, (which is 41 + 9), are labeled 149, 150, 151.

    If we do the same on level 3 (vertices 14 to 40) we have that the children of vertex 14 are 41, 42, 43, and for x = 0 to 26, the children of vertex 14 + x are 41 + 3x, 42 + 3x, 43 + 3x. 50 can be written as 41 + 3*3 so by putting x = 3 in the above we come to the conclusion that it is the first child of vertex 14+3=17.