308-360 Tutorial #2

Things to know before you start these problems

Deductive reasoning - from statements accepted as true, logically draw conclusions. If the theory is not compatible with reality, then the assumptions must indeed be untrue and the theory does not apply. Use deductive reasoning to formaulate many of the proofs regarding graphs.

The degree of a vertex is the number of incident edges it has.

The First theorem of graph theory relates degrees to edges. It states that the sum of the degrees of the vertices is twice the number of edges.
If every vertex of a graph has the same degree, then that graph is called regular. In an n-regular graph, all vertices have degree n. so, deg(G) = 2n for n regular graphs. so n is the number of edges. 2n choose n

Visit this site for a nearly complete set of Graph Definitions. You must know these definitions and understand how to use them to formulate proofs.

Also, if you do not know some term, check the Discrete Math Glossary.

CLR 23.2-7 The diameter of a tree T = (V,E) is given by max d(u,v) for all u,v in V; that is, the diameter is the largest of all shortest-path distances in the tree. Give an effficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.

To find the diameter of a graph G:

diameter=0
for each vertex v in V(G)
    do breadth-first search starting at v
        for each vertex u in V(G)
            if d(u,v) > diameter
                diameter = d(u,v)
return diameter


This runs in time O(|V| |E|).