### 4.3.4.7. three parameters/two final graphs

$\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}$

Proposition 135

$\begin{array}{cc}& \mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\hfill \\ & max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(3,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+\hfill \\ & max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)-2>{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇒\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\hfill \end{array}$

Proof 133 The quantity $max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(3,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)-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

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\hfill \\ & max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+\hfill \\ & max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)>{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇒\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\hfill \end{array}$

Proof 134 The quantity $max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)+max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)$ 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

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\hfill \\ & \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\notin \left[max\left({\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}-\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1,\hfill \\ & ⌊\frac{{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}+2}{2}⌋\right),\hfill \\ & {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}-1\right]\hfill \end{array}$

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.

$\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}$

Proposition 138

$\begin{array}{cc}& \mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\hfill \\ & max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)+max\left(3,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)+\hfill \\ & max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)-2>{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇒\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}\hfill \end{array}$

Proof 136 Similar to Proposition 135.

Proposition 139

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\hfill \\ & max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)+max\left(2,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}+1,\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}\right)+\hfill \\ & max\left(1,\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\right)>{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇒\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}\hfill \end{array}$

Proof 137 Similar to Proposition 136.

Proposition 140

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:\hfill \\ & \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\notin \left[max\left({\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}-\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}+1,\hfill \\ & ⌊\frac{{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}+2}{2}⌋\right),\hfill \\ & {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}-1\right]\hfill \end{array}$

Proof 138 Similar to Proposition 137.

$\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}$, ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{2}$

Proposition 141

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}\wedge \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\mathrm{mod}2=0⇒\hfill \\ & {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{2}\mathrm{mod}2={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}\mathrm{mod}2\hfill \end{array}$

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).

$\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}$, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}$, ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{1}$

Proposition 142

$\begin{array}{cc}& \mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}=\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}\wedge \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}\mathrm{mod}2=0⇒\hfill \\ & {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{1}\mathrm{mod}2={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}\mathrm{mod}2\hfill \end{array}$

Proof 140 Similar to Proposition 141.

$\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}$, ${\mathrm{𝐍𝐀𝐑𝐂}}_{2}$, ${\mathrm{𝐍𝐂𝐂}}_{1}$

Proposition 143

$\begin{array}{cc}& \mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}\wedge {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}>0:\hfill \\ & {\mathrm{𝐍𝐂𝐂}}_{1}=1⇔\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+{\mathrm{𝐍𝐀𝐑𝐂}}_{2}={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}\hfill \end{array}$

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.

$\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}$, ${\mathrm{𝐍𝐀𝐑𝐂}}_{2}$, ${\mathrm{𝐍𝐂𝐂}}_{1}$

Proposition 144

$\begin{array}{cc}& \mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}\wedge {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}>0:\hfill \\ & {\mathrm{𝐍𝐂𝐂}}_{2}=1⇔\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}+{\mathrm{𝐍𝐀𝐑𝐂}}_{1}={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}\hfill \end{array}$

Proof 142 Similar to Proposition 143.