$($ii$)$ Consider the following graph, which describes a flow network.

So Si

v$1$

v$2$

v$3$

v$4$

v$5$

v$6$

v$7$

$5(4)$

$5(3)$

v$8$

$4(4)$

$2(1)$

$3(3)$

$1(0)$

$5(0)$

$4(1)$

$1(0)$

$3(3)$

$2(2)$

$6(4)$

$8(3)$

$4(1)$

Ollscoil na hEireann, M$$a Nuad, Co$.$ Chill Dara, $$ Eire. $$

$2023$ National University of Ireland, Maynooth, Co$.$ Kildare, Ireland.

All rights reserved.

$3$

Here, the vertex labeled So is the source, and the vertex labeled Si is the sink.

The edge weightings indicate flow capacity, and the figures in brackets indicate

the current flow through the network.

Apply the Ford$-$Fulkerson procedure once to the above network, and draw a diagram to illustrate the new flow. Give full details of your considerations. Decide,

with justification, whether or not the new flow is maximal.