3
$\begingroup$

What is the maximum flow for any two vertices as source and sink in a complete graph?

My assumption is: V-1. Am I right?

1 Answers 1

3

I assume each edge has capacity 1, and that $V$ is the number of vertices. Only $V-1$ arcs leave the source, so $V-1$ is certainly an upper bound. It's not hard to see it can always be achieved, since for each vertex other than the sink there's a path from the source to that vertex to the sink, and there's a path direct from source to sink.