Cos 423 Problem Set No. 5-revised Due Wed. April 23, 2003 Spring 2003

4. 
   (See CLRS exercise 26.2-8, page 664.) (a) Show that a maximum flow in a network can always be found by a sequence of at most m augmenting paths.
   

Note: for purposes of this problem, an augmenting path is a path from s to t in the residual network, but the flow along it need not be maximum. (The augmentation need not saturate an edge.)

5. 
   Let G be a bipartite graph with maximum vertex degree d. Show that the edges of G can be colored with d colors so that no two edges having a common end vertex are the same color.