Proposition 165

Proof 163 Let $CC\left(G_1\right)=\{C{C}_a^1:a\in \left[\mathrm{𝐍𝐂𝐂}1\right]\}$ and $CC\left(G_2\right)=\{C{C}_a^2:a\in \left[\mathrm{𝐍𝐂𝐂}2\right]\}$ be respectively the set of connected components of the first and the second final graphs. Since the initial graph is a path, and since each arc of the initial graph belongs to the first or to the second final graphs (but not to both), there exists ${\left(A_i\right)}_{i\in [{\mathrm{𝐍𝐂𝐂}}_1+{\mathrm{𝐍𝐂𝐂}}_2]}$ and there exists $j\in \left[2\right]$ such that $A_i\in CC\left(G_{1+\left(j\mathrm{mod}2\right)}\right)$, for $i\mathrm{mod}2=0$ and $A_i\in CC\left(G_{1+\left(\right(j+1\left)\mathrm{mod}2\right)}\right)$ for $i\mathrm{mod}2=1$ and $A_i\cap A_{i+1}\ne \varnothing$ for $i\in [{\mathrm{𝐍𝐂𝐂}}_1+{\mathrm{𝐍𝐂𝐂}}_2-1]$.

By inclusion-exclusion principle, since $A_i\cap A_j=\varnothing$ whenever $j\ne i+1$, we obtain ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}={\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}1\right]}|C{C}_a^1|+{\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}2\right]}|C{C}_a^2|-{\Sigma }_{i\in [\mathrm{𝐍𝐂𝐂}1+\mathrm{𝐍𝐂𝐂}2-1]}|A_i\cap A_{i+1}|$. Since $|A_i\cap A_{i+1}|$ is equal to 1 for every well defined $i$, we obtain ${\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}1\right]}|C{C}_a^1|+{\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}2\right]}\left|C{C}_a^2\right|={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}+\mathrm{𝐍𝐂𝐂}1+\mathrm{𝐍𝐂𝐂}2-1$.

Since $\alpha ·\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1+\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1+\beta ·\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_2+\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_2\le {\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}1\right]}|C{C}_a^1|+{\Sigma }_{a\in \left[\mathrm{𝐍𝐂𝐂}2\right]}\left|C{C}_a^2\right|$ the result follows.

Proposition 166

Proof 164 Similar to Proposition 165.