# Values of $s-t$ flows and cuts

$$G = (V, A)$$ is a directed graph where all arcs in $$A$$ have a capacity of $$1$$. The shortest length path in $$G$$ from $$s$$ to $$t$$ consists of exactly $$d$$ arcs. G has a total of $$m$$ arcs and $$n$$ vertices.

(a) Prove that the maximum $$s-t$$ flow has value $$O\left(\frac{m}{d}\right)$$.

(b) Prove that the minimum capacity $$s-t$$ cut has value $$O\left(\frac{n^2}{d^2}\right)$$.

For part a), I was thinking that since there are going to be $$m$$ arcs total, the value would be in the order of $$m$$. I am thinking that by diving this $$m$$ by $$d$$, we get the total number of arcs used when gathering the maximum $$s-t$$ flow through the Ford-Fulkerson algorithm. But I am not entirely sure how to prove this or if this is actually the case.

For part b), I am also quite confused as I am not sure how I should go about finding either of the numerator or denominator. I was thinking about splitting the graph in two to represent the cut but that has not been helping me to compute the value.

I was also wondering that since all arcs have a capacity of $$1$$, wouldn't the value of the maximum flow and the minimum cut both just be $$1$$? So do I have to show that both $$\frac{m}{d}$$ and $$\frac{n^2}{d^2}$$ are equal to $$1$$?

I would greatly appreciate any help!

• Neither of these questions are, as you've stated them, asking you for a run-time. – Misha Lavrov Feb 3 at 2:00
• Yes sorry. My apologies. The question is asking me to compute the value. But I am not sure how to approach this using the big $O$. – esterrobson Feb 3 at 2:03
• So, please edit your question so it doesn't mention runtime. – Gerry Myerson Feb 3 at 5:39
• @GerryMyerson I have just edited it. – esterrobson Feb 3 at 15:52