1) Graphs can have more than one maximum flow. Let N(G) be the number of maximum flows for graph G = (V, E). Show that for any positive integer k you can find a graph where

N(G)/|V | > k.

2) Let G = (V, E) be a tree graph with root s with finite capacities assigned to each edge. Suppose we add an additional vertex t and edges with infinite capacity from all leaves in G to t. Find an O(|V |) algorithm to determine the maximum flow from s to t.