# Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of all edges is always an integer, and so is the flow. Is there an algorithm that can find a maximum flow in this new network with complexity O(|E|), where E is the set of edges? If so, what would this algorithm look like?

Since you only have $$7$$ edges (and hence at most $$8$$ vertices reachable from the flow source) any flow algorithm whose runtime is independent of the edge weights will take time $$O(1) = O(|E|)$$. See, for example, the Edmonds-Karp algorithm.
• Consider the undirected version of your input network. The number of edges in this network is at most $7$ by hypothesis. Consider the connected component $C$ containing the source. Pick any spanning tree $T$ of $C$. The number of edges in the tree is a lower bound to the number of edges in $C$. A tree with $n$ vertices has exactly $n-1$ edges. Therefore if $C$ has $9$ or more vertices, then $T$ has 8 edges, and both $C$ and the input network contain at least $8$ edges. Oct 12 '21 at 10:43
• Then how can we assume that there exists a component $C$ in a graph that is not connected? Oct 12 '21 at 10:56