### 4.3.4.4. four parameters/one final graph

Proposition 110 Let $\mathrm{\Xi ±}$ denote $max\left(0,\mathrm{\pi \pi \pi }-1\right)$.

$\mathrm{\pi \pi \pi \pi }\beta €\mathrm{\Xi ±}Β·\mathrm{\pi \pi \pi }_{\mathrm{\pi \pi \pi }}^{2}+\mathrm{\pi \pi \pi }_{\mathrm{\pi \pi \pi }}^{2}$

Proof 110 We construct $\mathrm{\pi \pi \pi }-1$ connected components with $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ vertices and one connected component with $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ vertices. ${n}^{2}$ corresponds to the maximum number of arcs in a connected component. $n$, $2Β·n-2$, $\frac{nΒ·\left(n+1\right)}{2}$, $\frac{nΒ·\left(n+1\right)}{2}$, $\frac{nΒ·\left(n-1\right)}{2}$, $\frac{nΒ·\left(n-1\right)}{2}$, ${n}^{2}-n$, $2Β·n$ and $n-1$ respectively correspond to the maximum number of arcs in a connected component of $n$ vertices according to the fact that we use the arc generator $\mathrm{\pi Ά\pi Ό\pi  \pi Ά\pi \pi Ό\pi }$, $\mathrm{\pi Ά\pi »\pi ΄\pi Ό\pi }$, $\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\left(\beta €\right)$ $\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\left(\beta ₯\right)$ $\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\left(<\right)$ $\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}\left(>\right)$ $\mathrm{\pi Ά\pi \pi Ά\pi Ώ\pi Έ}$ or $\mathrm{\pi \pi ΄\pi \pi »}$.

Proposition 111

$\mathrm{\pi \pi \pi }>0\beta \mathrm{\pi \pi \pi \pi }\beta ₯\left(\mathrm{\pi \pi \pi }-1\right)Β·max\left(1,\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }-1\right)+max\left(1,\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }-1\right)$

Proof 111 (165) We construct $\mathrm{\pi \pi \pi }-1$ connected components with $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ vertices and one connected component with $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ vertices. The quantity $max\left(1,n-1\right)$ corresponds to the minimum number of arcs in a connected component of $n$ $\left(n>0\right)$ vertices.

Proposition 112

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\beta €max\left(0,\mathrm{\pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$

Proposition 113

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\beta ₯max\left(0,\mathrm{\pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$

Proposition 114

$\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi }Β·max\left(0,\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }-1\right)$

Proof 114 Since a connected component contains at most $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ vertices and since it does not contain any isolated vertex and since a same vertex cannot be both a sink and a source a connected component involves at most $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }-1$ sinks and sources all together. Thus the result follows.

Proposition 115

$\begin{array}{cc}& \mathrm{\pi \pi \pi \pi }\beta €max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_{\mathrm{\pi \pi \pi \pi }}^{2}+\mathrm{\pi \pi \pi }_{\mathrm{\pi \pi \pi \pi }}^{2}+\\ & max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }+\\ & \mathrm{\pi \pi \pi }_{\mathrm{\pi \pi \pi \pi }}^{2}Β·\frac{max\left(0,\mathrm{\pi \pi \pi \pi }-2\right)Β·max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)}{2}\end{array}$

Proof 115 We assume that we have at least two strongly connected components (the case with one being obvious). Let ${\left(SC{C}_{i}\right)}_{i\beta \left[\mathrm{\pi \pi \pi }\left(G\right)\right]}$ be the family of strongly connected components of $G$. Then $|E\left(G\right)|\beta €{\beta }_{i\beta \left[\mathrm{\pi \pi \pi }\left(G\right)\right]}|E\left(G\left[SC{C}_{i}\right]\right)|+k$, where $k$ is the number of arcs between the distinct strongly connected components of $G$. For any strongly connected component $SC{C}_{i}$ the number of arcs it has with the other strongly connected components is bounded by $|SC{C}_{i}|Β·\left(|V\left(G\right)-SC{C}_{i}|\right)$. Consequently, $k\beta €\frac{1}{2}Β·{\beta }_{i\beta \left[\mathrm{\pi \pi \pi }\left(G\right)\right]}|SC{C}_{i}|Β·\left(|V\left(G\right)-SC{C}_{i}|\right)$. W.l.o.g. we assume $|SC{C}_{1}|=\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$. Then we get $k\beta €\frac{1}{2}Β·\left(\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }Β·\left(\mathrm{\pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }Β·\left(\left(\mathrm{\pi \pi \pi }-2\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }\right)\right)$.

Proposition 116

$\mathrm{\pi \pi \pi \pi }\beta ₯max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$

Proof 116 Let ${\left(SC{C}_{i}\right)}_{i\beta \left[\mathrm{\pi \pi \pi }\left(G\right)\right]}$ be the family of strongly connected components of $G$, as $|E\left(G\right)|\beta ₯{\beta }_{i\beta \left[\mathrm{\pi \pi \pi }\left(G\right)\right]}|E\left(G\left[SC{C}_{i}\right]\right)|$, we obtain the result since in a strongly connected graph the number of edges is at least its number of vertices.

Proposition 117

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\beta €max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$

Proposition 118

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\beta ₯max\left(0,\mathrm{\pi \pi \pi \pi }-1\right)Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }+\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$

Proposition 119 Let $\mathrm{\Xi ±}$, $\mathrm{\Xi ²}$ and $\mathrm{\Xi ³}$ respectively denote $max\left(0,\mathrm{\pi \pi \pi }-1\right)$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathrm{\Xi ±}Β·\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ and $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$.

$\mathrm{\pi \pi \pi \pi }\beta €\mathrm{\Xi ±}Β·{\mathrm{\Xi ³}}^{2}+{\mathrm{\Xi ²}}^{2}$

Proof 119 For proving inequalityΒ 174 we proceed by induction on the number of vertices of $G$. First note that if all the connected components are reduced to one element the result is obvious. Thus we assume that the number of vertices in the maximal sized connected component of $G$ is at least 2. Let $x$ be an element of the maximal sized connected component of $G$. Then, $G-x$ satisfies $\mathrm{\Xi ±}\left(G-x\right)=\mathrm{\Xi ±}\left(G\right)$, $\mathrm{\Xi ³}\left(G-x\right)=\mathrm{\Xi ³}\left(G\right)$ and $\mathrm{\Xi ²}\left(G-x\right)=\mathrm{\Xi ²}\left(G\right)-1$. Since by induction hypothesis $|E\left(G-x\right)|\beta €\mathrm{\Xi ±}\left(G-x\right)Β·\mathrm{\Xi ³}{\left(G-x\right)}^{2}+\mathrm{\Xi ²}{\left(G-x\right)}^{2}$, and since the number of arcs of $G$ incident to $x$ is at most $2Β·\left(\mathrm{\Xi ²}\left(G\right)-1\right)+1$, we have that $|E\left(G\right)|\beta €\mathrm{\Xi ±}\left(G\right)Β·\mathrm{\Xi ³}{\left(G\right)}^{2}+{\left(\mathrm{\Xi ²}\left(G\right)-1\right)}^{2}+2Β·\left(\mathrm{\Xi ²}\left(G\right)-1\right)+1$. And thus the result follows.

Proposition 120

$\begin{array}{cc}\hfill \mathrm{\pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi }-1& +\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }+1\right)Β·\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi }+1\right)\hfill \\ & +\frac{\left(\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi }+1\right)Β·\left(\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi }\right)}{2}\hfill \end{array}$

Proof 120 We proceed by induction on $T\left(G\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-|X|-\left(\mathrm{\pi \pi \pi }\left(G\right)-1\right)$, where $X$ is any connected component of $G$ of maximum cardinality. For $T\left(G\right)=0$ then either $\mathrm{\pi \pi \pi }\left(G\right)=1$ and thus the formula is clearly true, by PropositionΒ 145 or all the connected components of $G$, but possibly $X$, are reduced to one element. Since isolated vertices are not allowed, again by PropositionΒ 145 applied on $G\left[X\right]$, the formula holds indeed $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\left[X\right]\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-\left(\mathrm{\pi \pi \pi }\left(G\right)-1\right)$ and $\mathrm{\pi \pi \pi \pi }\left(G\left[X\right]\right)=\mathrm{\pi \pi \pi \pi }\left(G\right)-\left(\mathrm{\pi \pi \pi }\left(G\right)-1\right)$.

Assume that $T\left(G\right)\beta ₯1$. Then there exists $Y$, a connected component of $G$ distinct from $X$, with more than one vertex.

• Firstly assume that $G\left[Y\right]$ is strongly connected. Let $y\beta Y$ and let ${G}^{\text{'}}$ be the graph such that $V\left({G}^{\text{'}}\right)=V\left(G\right)$ and $E\left({G}^{\text{'}}\right)$ is defined by:

• For all $Z$ connected components of $G$ distinct from $X$ and $Y$ we have ${G}^{\text{'}}\left[Z\right]=G\left[Z\right]$.

• With ${X}^{\text{'}}=X\beta ͺ\left(Y-\left\{y\right\}\right)$ and ${Y}^{\text{'}}=\left\{y\right\}$, we have $E\left({G}^{\text{'}}\left[{Y}^{\text{'}}\right]\right)=\left\{\left(y,y\right)\right\}$, $E\left({G}^{\text{'}}\left[{X}^{\text{'}}\right]\right)=E\left(G\left[X\right]\right)\beta ͺ\left\{\left(z,x\right):z\beta Y-\left\{y\right\},x\beta X\right\}\beta ͺ\left\{\left(z,t\right):z,t\beta Y-\left\{y\right\}\right\}$.

Clearly we have that $|E\left({G}^{\text{'}}\right)|-|E\left(G\right)|\beta ₯\left(|Y|-1\right)Β·|X|-2Β·\left(|Y|-1\right)$ and since $|X|\beta ₯|Y|\beta ₯2$, the difference is positive or null. Now as $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)$, $\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi }\left(G\right)$, $\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi }\left(G\right)$ (since ${G}^{\text{'}}\left[Y-\left\{y\right\}\right]$ is strongly connected because $E\left({G}^{\text{'}}\left[Y-\left\{y\right\}\right]\right)=\left\{\left(z,t\right):z,t\beta Y-\left\{y\right\}\right\}$ and since the reduced graph of the strongly connected components of ${G}^{\text{'}}\left[{X}^{\text{'}}\right]$ is exactly the reduced graph of the strongly connected components of $G\left[X\right]$ to which a unique source has been added) and as $T\left({G}^{\text{'}}\right)\beta €T\left(G\right)-1$, the result holds by induction hypothesis.

• Secondly assume that $G\left[Y\right]$ is not strongly connected. Let $Z\beta Y$ such that $Z$ is a strongly connected component of $G\left[Y\right]$ corresponding to a source in the reduced graph of the strongly connected components of $G\left[Y\right]$. Let ${G}^{\text{'}}$ be the graph such that $V\left({G}^{\text{'}}\right)=V\left(G\right)$ and $E\left({G}^{\text{'}}\right)$ is defined by:

• For all $W$ connected components of $G$ distinct from $X$ and $Y$ we have ${G}^{\text{'}}\left[W\right]=G\left[W\right]$.

• With ${X}^{\text{'}}=X\beta ͺZ$ and ${Y}^{\text{'}}=Y-Z$, we have $E\left({G}^{\text{'}}\left[{Y}^{\text{'}}\right]\right)=E\left(G\left[{Y}^{\text{'}}\right]\right)$ if $|{Y}^{\text{'}}|>1$ and $E\left({G}^{\text{'}}\left[{Y}^{\text{'}}\right]\right)=\left\{\left(y,y\right)\right\}$ if ${Y}^{\text{'}}=\left\{y\right\}$. $E\left({G}^{\text{'}}\left[{X}^{\text{'}}\right]\right)=E\left(G\left[X\right]\right)\beta ͺ\left\{\left(z,x\right):z\beta Z,x\beta X\right\}$.

Clearly we have that $|E\left({G}^{\text{'}}\right)|-|E\left(G\right)|\beta ₯|Z|Β·|X|-|Z|Β·\left(|Y|-|Z|\right)$ and since $|X|>|Y|-|Z|$, the difference is strictly positive. Now as $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)$, $\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi }\left(G\right)$, $\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi }\left(G\right)$ and as $T\left({G}^{\text{'}}\right)\beta €T\left(G\right)-1$, the result holds by induction hypothesis.

Proposition 121

$\mathrm{\pi \pi \pi \pi }\beta ₯\mathrm{\pi \pi \pi \pi \pi \pi \pi }-max\left(0,min\left(\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi }\right)\right)$

Proof 121 We prove that the invariant is valid for any digraph $G$. First notice that for an operational behaviour, since we cannot assume that PropositionΒ 55 (i.e.,Β $\mathrm{\pi \pi \pi }\left(G\right)\beta €\mathrm{\pi \pi \pi \pi }\left(G\right)$) was already triggered, we use the $max$ operator. But since any strongly connected component is connected, then $\mathrm{\pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)$ is never negative. Consequently we only show by induction on $\mathrm{\pi \pi \pi \pi }\left(G\right)$ that $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-min\left(\mathrm{\pi \pi \pi }\left(G\right),\mathrm{\pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)\right)$. To begin notice that if $X$ is a strongly (non void) connected component then either $\mathrm{\pi \pi \pi \pi }\left(G\left[X\right]\right)\beta ₯|X|$ or $\mathrm{\pi \pi \pi \pi }\left(G\left[X\right]\right)=0$ and in this latter case we have that both $|X|=1$ and $X$ is strictly included in a connected component of $G$ (recall that isolated vertices are not allowed). Thus we can directly assume that $\mathrm{\pi \pi \pi \pi }\left(G\right)=k>1$.

First, consider that there exists a connected component of $G$, say $X$, which is also strongly connected. Let ${G}^{\text{'}}=G-X$, consequently we have $\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi }\left(G\right)-1$, $\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi }\left(G\right)-1$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-|X|$, and $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯|X|+\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)$. Then $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯|X|+\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)-min\left(\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right),\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)-\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)\right)$ and thus $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-min\left(\mathrm{\pi \pi \pi }\left(G\right)-1,\mathrm{\pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)\right)$, which immediately gives the result.

Second consider that any strongly connected component is strictly included in a connected component of $G$. Then, either there exists a strongly connected component $X$ such that $|X|\beta ₯2$. Let ${G}^{\text{'}}=G-X$, consequently we have $\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi }\left(G\right)-1$, $\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi }\left(G\right)$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-|X|$, and $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯|X|+1+\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)$. Then $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯|X|+1+\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left({G}^{\text{'}}\right)-min\left(\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right),\mathrm{\pi \pi \pi \pi }\left({G}^{\text{'}}\right)-\mathrm{\pi \pi \pi }\left({G}^{\text{'}}\right)\right)$ and thus $\mathrm{\pi \pi \pi \pi }\left(G\right)\beta ₯\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)+1-min\left(\mathrm{\pi \pi \pi }\left(G\right),\mathrm{\pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)+1\right)$, which immediately gives the result. Or, all the strongly connected components are reduced to one element, so we have $\mathrm{\pi \pi \pi \pi }\left(G\right)=\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)$, and thus we obtain that $\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-min\left(\mathrm{\pi \pi \pi }\left(G\right),\mathrm{\pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)\right)=min\left(\mathrm{\pi \pi \pi }\left(G\right),\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(G\right)-\mathrm{\pi \pi \pi }\left(G\right)\right)$, which gives the result by for example PropositionΒ 99Β (143).

This bound is tight: take for example any circuit.

Proposition 122

$\begin{array}{cc}\hfill \mathrm{\pi \pi \pi \pi }\beta €{\mathrm{\pi \pi \pi \pi \pi \pi \pi }}^{2}& -\mathrm{\pi \pi \pi \pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi \pi \pi \pi \pi }\hfill \\ & -\mathrm{\pi \pi \pi \pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi \pi \pi }+\mathrm{\pi \pi \pi \pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi \pi \pi }\hfill \end{array}$

Proof 122 Since the maximum number of arcs of a digraph is ${\mathrm{\pi \pi \pi \pi \pi \pi \pi }}^{2}$, and since:

• No vertex can have a source as a successor we lose $\mathrm{\pi \pi \pi \pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ arcs,

• No sink can have a successor we lose $\mathrm{\pi \pi \pi \pi \pi \pi \pi }Β·\mathrm{\pi \pi \pi \pi \pi }$ arcs.

In these two sets of arcs we count twice the arcs from the sinks to the sources, so we finally get a maximum number of arcs corresponding to the right-hand side of the inequality to prove.