### 4.3.4.2. two parameters/one final graph

Proposition 14

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}=0$

Proof 14

Proposition 15

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}\le \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$

Proof 15 $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$ is a lower bound of the size of the largest connected component since the largest strongly connected component is for sure included within a connected component.

Proposition 16

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=0$

Proof 16

Proposition 17

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\le \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$

Proof 17

Proposition 18

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐀𝐑𝐂}=0$

Proof 18

Proposition 19

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}>0⇒\mathrm{𝐍𝐀𝐑𝐂}\ge max\left(1,\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-1\right)$

$\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}:\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}>0⇒\mathrm{𝐍𝐀𝐑𝐂}\ge max\left(1,2·\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-2\right)$

$\mathrm{𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}^{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-1$

Proof 19

(19) $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-1$ arcs are needed to connect $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$ vertices that belong to a given connected component containing at least two vertices. And one arc is required for a connected component containing a single vertex.

(20) Similarly, when the graph is symmetric, $2·\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-2$ arcs are needed to connect $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$ vertices that belong to a given connected component containing at least two vertices.

(21) Finally, when the graph is reflexive, symmetric and transitive, $\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}^{2}$ arcs are needed to connect $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$ vertices that belong to a given connected component.

(22) When the initial graph corresponds to a path, the minimum number of arcs of a connected component involving $n$ vertices is equal to $n-1$.

Proposition 20

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇒\mathrm{𝐍𝐒𝐈𝐍𝐊}=0$

Proof 20

Proposition 21

$\mathrm{𝐍𝐒𝐈𝐍𝐊}\ge 1⇒\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}\ge 2$

Proof 21 Since we do not have any isolated vertex a sink is connected to at least one other vertex. Therefore, if the graph has a sink, there exists at least one connected component with at least two vertices.

Proposition 22

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇒\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}=0$

Proof 22

Proposition 23

$\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}\ge 1⇒\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}\ge 2$

Proof 23 Since we do not have any isolated vertex a source is connected to at least one other vertex. Therefore, if the graph has a source, there exists at least one connected component with at least two vertices.

Proposition 24

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 24

Proposition 25

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\ge \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$

Proposition 26

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=0$

Proof 26

Proposition 27

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}\le \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$

Proof 27

Proposition 28

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐍𝐀𝐑𝐂}=0$

Proof 28

Proposition 29

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$

$\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}:\mathrm{𝐍𝐀𝐑𝐂}\ge 2·\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$

$\mathrm{𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐒𝐂𝐂}}^{2}$

Proof 29 (32) In a strongly connected component at least one arc has to leave each vertex. Since we have at least one strongly connected component of $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$ vertices this leads to the previous inequality.

Proposition 30

$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 30

Proposition 31

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\ge \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$

Proof 31 By definition of $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$.

Proposition 32

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=0$

Proof 32

Proposition 33

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$

Proof 33 By construction $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}$ is an upper bound of the number of vertices of the smallest strongly connected component.

Proposition 34

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐀𝐑𝐂}=0$

Proof 34

Proposition 35

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}>0⇒\mathrm{𝐍𝐀𝐑𝐂}\ge max\left(1,\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}-1\right)$

$\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}:\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}>0⇒\mathrm{𝐍𝐀𝐑𝐂}\ge max\left(1,2·\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}-2\right)$

$\mathrm{𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}^{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}-1$

Proof 35 Similar to Proposition 19.

Proposition 36

$\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\left(\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+1\right)·\mathrm{𝐍𝐂𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}+1$

Proof 36 By definition of $\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$.

Proposition 37

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 37

Proposition 38

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}$

Proposition 39

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\notin \left[min\left(⌊\frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}{2}⌋,⌊\frac{{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-1}{2}⌋\right)+1,\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1\right]$

Proof 39 On the one hand, if $\mathrm{𝐍𝐂𝐂}\le 1$, we have that $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\ge \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$. On the other hand, if $\mathrm{𝐍𝐂𝐂}>1$, we have that $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ and that $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+1\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}$, which by isolating $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}$ and by grouping the two inequalities leads to $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\le min\left(⌊\frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}{2}⌋,⌊\frac{{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-1}{2}⌋\right)$. The result follows.

Proposition 40

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐍𝐀𝐑𝐂}=0$

Proof 40

Proposition 41

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$

$\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}:\mathrm{𝐍𝐀𝐑𝐂}\ge 2·\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$

$\mathrm{𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎}:\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐒𝐂𝐂}}^{2}$

Proof 41 Similar to Proposition 29.

Proposition 42

$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 42

Proposition 43

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$

Proposition 44

$\mathrm{𝐍𝐀𝐑𝐂}=0⇔\mathrm{𝐍𝐂𝐂}=0$

Proof 44

Proposition 45

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐍𝐂𝐂}$

Proof 45 Each connected component contains at least one arc (since, by hypothesis, each vertex has at least one arc).

Proposition 46

$\mathrm{𝐍𝐀𝐑𝐂}=0⇔\mathrm{𝐍𝐒𝐂𝐂}=0$

Proof 46

Proposition 47

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐍𝐒𝐂𝐂}$

$\mathrm{𝚗𝚘}\mathrm{𝚕𝚘𝚘𝚙}:\mathrm{𝐍𝐀𝐑𝐂}\ge 2·\mathrm{𝐍𝐒𝐂𝐂}$

Proof 47 57 (respectively 58) holds since each strongly connected component contains at least one (respectively two) arc(s).

Proposition 48

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐍𝐒𝐈𝐍𝐊}$

Proof 48 Since isolated vertices are not allowed, each sink has a distinct ingoing arc.

Proposition 49

$\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$

Proof 49 Since isolated vertices are not allowed, each source has a distinct outgoing arc.

Proposition 50

$\mathrm{𝐍𝐀𝐑𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 50

Proposition 51

$\mathrm{𝐍𝐀𝐑𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐼𝑅𝐶𝑈𝐼𝑇}:\mathrm{𝐍𝐀𝐑𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐻𝐴𝐼𝑁}:\mathrm{𝐍𝐀𝐑𝐂}\le 2·\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-2$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\le \right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}+1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\ge \right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}+1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(<\right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(>\right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\ne \right):\mathrm{𝐍𝐀𝐑𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^{2}-\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝑌𝐶𝐿𝐸}:\mathrm{𝐍𝐀𝐑𝐂}\le 2·\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\mathrm{𝐍𝐀𝐑𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1$

Proof 51 62 holds since each vertex of a digraph can have at most $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ successors. The next items correspond to the maximum number of arcs that can be achieved according to a specific arc generator.

Note that, when the equality is reached in 62, the corresponding extreme graph is in fact the graph initially generated. The same observation holds for inequalities 63 to 71. As a consequence all $U$-arcs have to be turned into $T$-arcs.

Proposition 52

$2·\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 52 By induction on the number of vertices of a graph $G$:

1. If $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G\right)$ is equal to 1 or 2 Proposition 52 holds.

2. Assume that $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G\right)\ge 3$.

• Assume there exists a vertex $v$ such that, if we remove $v$, we do not create any isolated vertex in the remaining graph. We have $\mathrm{𝐍𝐀𝐑𝐂}\left(G\right)\ge \mathrm{𝐍𝐀𝐑𝐂}\left(G-v\right)+1$. Thus $2·\mathrm{𝐍𝐀𝐑𝐂}\left(G\right)\ge 2·\mathrm{𝐍𝐀𝐑𝐂}\left(G-v\right)+1$. Since by induction hypothesis $2·\mathrm{𝐍𝐀𝐑𝐂}\left(G-v\right)\ge \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G-v\right)=\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G\right)-1$ the result holds.

• Otherwise, all the connected components of $G$ are reduced to two elements with only one arc. We remove one of such connected component $\left(v,w\right)$.

Thus $\mathrm{𝐍𝐀𝐑𝐂}\left(G\right)=\mathrm{𝐍𝐀𝐑𝐂}\left(G-\left\{v,w\right\}\right)+1$. As by induction hypothesis, $2·\mathrm{𝐍𝐀𝐑𝐂}\left(G-\left\{v,w\right\}\right)\ge \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G-\left\{v,w\right\}\right)=\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\left(G\right)-2$ the result holds.

Note that, when the equality is reached in 52, the corresponding extreme graph is in fact a perfect matching of the graph. As a consequence all $U$-arcs that do not belong to any perfect matching have to be turned into $F$-arcs.

Proposition 53

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐿𝑂𝑂𝑃}:\mathrm{𝐍𝐀𝐑𝐂}=\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proposition 54

$\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐒𝐂𝐂}=0$

Proof 54

Proposition 55

$\mathrm{𝐍𝐂𝐂}\le \mathrm{𝐍𝐒𝐂𝐂}$

Proof 55 Holds since each connected component contains at least one strongly connected component.

Note that, when the equality is reached in 55, each connected component of the corresponding extreme graph is strongly connected. As a consequence all sink vertices of the graph induced by the $T$-vertices and the $T$-arcs should have at least one successor.

Proposition 56

$\mathrm{𝐍𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 56

Proposition 57

$\mathrm{𝐍𝐂𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝚗𝚘}\mathrm{𝚕𝚘𝚘𝚙}:2·\mathrm{𝐍𝐂𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 57 77 (respectively 78) holds since each connected component contains at least one (respectively two) vertex.

Note that, when the equality is reached in 77, the corresponding extreme graph does not contain any arc between two distinct vertices. As a consequence any $U$-arc between two distinct vertices is turned into a $F$-vertex.

Proposition 58

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\hfill \\ & \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\left(\mathrm{𝐍𝐂𝐂}-1\right)\hfill \end{array}$

Proof 58 Holds since between two “consecutive” connected components of the initial graph there is at least one vertex that is missing.

Proposition 59

$\mathrm{𝐍𝐒𝐂𝐂}\ge \mathrm{𝐍𝐒𝐈𝐍𝐊}+1$

Proof 59 Since each sink cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-sink vertex is required the result follows.

Proposition 60

$\mathrm{𝐍𝐒𝐂𝐂}\ge \mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}+1$

Proof 60 Since each source cannot belong to a circuit and since no isolated vertex is allowed at least one extra non-source vertex is required the result follows.

Proposition 61

$\mathrm{𝐍𝐒𝐂𝐂}=0⇔\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0$

Proof 61

Proposition 62

$\mathrm{𝐍𝐒𝐂𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 62 Proposition 62 holds since each strongly connected component contains at least one vertex.

Proposition 63

$\mathrm{𝚊𝚌𝚢𝚌𝚕𝚒𝚌}:\mathrm{𝐍𝐒𝐂𝐂}=\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 63 In a directed acyclic graph we have that each vertex corresponds to a strongly connected component involving only that vertex.

Proposition 64

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0⇒\mathrm{𝐍𝐒𝐈𝐍𝐊}=0$

Proof 64

Proposition 65

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}>0⇒\mathrm{𝐍𝐒𝐈𝐍𝐊}<\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 65 Holds since each sink must have a predecessor that cannot be a sink and since each vertex has at least one arc.

Proposition 66

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}=0⇒\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}=0$

Proof 66

Proposition 67

$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}>0⇒\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}<\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

Proof 67 Holds since each source must have a successor that cannot be a source and since each vertex has at least one arc.