1.   (a) Decide which of the following statements is true or false, by proving it or by giving a counterexample:  (i) f (n) = Ω(n log n) implies f (n) = Ω(n2 ) and (ii) g(n) = O(e,log n) implies g(n) = Θ(n/ log n).

(b) Let T (V, E) be a rooted tree in which every vertex has degree at most 3. Assume the longest simple path starting at the root has h edges. Show that T has at most 3h  leaves.

(c)  Solve the recurrence T (n) = T (n/2) + 2T (n/8) + n3 . You may assume that n is a power of 2. Is this recurrence covered by the general theorem?

2.   (a)  Show that if a graph G(V, E) has two distinct spanning trees, then IEI > IV I. Is it true that if G has three distinct spanning trees, then IEI > IV I + 1?

(b) Let G(V, E) be a graph with cost function c : E → R and T a minimum cost spanning tree.  Assume c(e)  > 0 for all e  e E.   Does it follow that T is a minimum cost spanning tree in G for the cost function c2 (e)?

(c) In the network G(V, E) the vertices are s, a, b, c, d, e, t with s the source and t the sink.   The arcs and their capacities are given by u(sa)  =  3, u(sc)  = 2, u(se) = 3, u(ab) = 4, u(ba) = 2, u(ac) =  1, u(ce) = 4, u(bt) = 3, u(db) = 2, u(dt) = 1, u(ed) = 1, u(et) = 2. We define the flow x : E → R by x = 1 on every arc except x(ce) = 2.  Is this flow feasible?  What is the total flow fx ? Find a maximal s - t flow and a minimal s - t cut in this network.

3.   (a) Explain how the shortest augmenting path algorithm works.   State the two lemmas needed for its validation. Show how they imply that the complexity of the algorithm is O(mn3 ).

(b) Let G be a bipartite graph with bipartition classes P and Q. G has 16 vertices of degree 5, the rest of the vertices have degree 8.  All vertices with degree 8 are in Q. How many vertices can G have?

(c) Let G(V, E) be a bipartite graph with bipartition classes P and Q.  Assume that deg p = a for every p e P and deg q = b for every q e Q and a > b. Show that G contains a matching of size IP I. Does it also contain a matching of size IQI?