Proposition 135

Proof 133 The quantity $max(2,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1)+max(3,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1+1,\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1)+max(2,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_2)-2$ corresponds to the minimum number of variables needed for building two non-empty connected components of respective size $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1$ and $\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$ such that $\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$ is strictly greater than $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1$. If this quantity is greater than the total number of variables we have that $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1=\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$.

Proposition 136

Proof 134 The quantity $max(1,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1)+max(2,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1+1,\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1)+max(1,\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_2)$ corresponds to the minimum number of variables needed for building two non-empty connected components of respective size $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1$ and $\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$ such that $\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$ is strictly greater than $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1$. If this quantity is greater than the total number of variables we have that $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1=\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$.

Proposition 137

Proof 135 A value $v$ is not a possible number of vertices for the smallest connected component of type 2 if the following two conditions hold:

• $v+\mathrm{𝐌𝐀𝐗}\_{\mathrm{𝐍𝐂𝐂}}_1$ does not allow to cover all the vertices of the initial graph: we need at least one extra connected component of type 1 or 2.

• If we add an additional connected component of type 1 or 2 we exceed the number of vertices of the initial graph.

Proposition 138

Proof 136 Similar to Proposition 135.

Proposition 139

Proof 137 Similar to Proposition 136.

Proposition 140

Proof 138 Similar to Proposition 137.

Proposition 141

Proof 139 If the number of vertices of the first graph is even then the number of vertices of the second graph has the same parity as the number of vertices of the initial graph (since a vertex of the initial graph belongs either to the first graph, either to the second graph (but not to both).

Proposition 142

Proof 140 Similar to Proposition 141.

Proposition 143

Proof 141 When $\mathrm{𝐌𝐈𝐍}\_{\mathrm{𝐍𝐂𝐂}}_1+{\mathrm{𝐍𝐀𝐑𝐂}}_2={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}$ there is no more room for an extra connected component for the first final graph.

Proposition 144

Proof 142 Similar to Proposition 143.