### 4.3.4.6. two parameters/two final graphs

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

Proposition 125

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

Proof 123 We show that the conjunction $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\ge {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$ and $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\le \mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}-1$ leads to a contradiction.

Since $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\le \mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}-1$ we have that $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\ne \mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$ and the minimum required size for the different groups is $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}+1+\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$. This minimum required size should not exceed the number of vertices ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}$ of the initial graph. But since, by hypothesis, $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}\ge {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}$, this is impossible.

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

Proposition 126

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

Proof 124 Similar to Proposition 125.

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

Proposition 127

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{2}>0$

$\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{1}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{2}>0$

Proof 125 (186) Since we have the precondition $\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$, we know that each vertex of the initial graph belongs to the first or to the second final graphs (but not to both).

1. On the one hand, if the largest connected component of the first final graph cannot contain all the vertices of the initial graph, then the second final graph has at least one connected component.

2. On the other hand, if the second final graph has at least one connected component then the largest connected component of the first final graph cannot be equal to the initial graph.

(187) holds for a similar reason.

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

Proposition 128

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{1}>0$

$\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}_{2}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{1}>0$

Proof 126 Similar to Proposition 127.

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

Proposition 129

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{1}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{2}>0$

Proof 127 Since we have the precondition $\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$, we know that each vertex of the initial graph belongs to the first or to the second final graphs (but not to both).

1. On the one hand, if the smallest connected component of the first final graph cannot contain all the vertices of the initial graph, then the second final graph has at least one connected component.

2. On the other hand, if the second final graph has at least one connected component then the smallest connected component of the first final graph cannot be equal to the initial graph.

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

Proposition 130

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}_{2}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}⇔{\mathrm{𝐍𝐂𝐂}}_{1}>0$

Proof 128 Similar to Proposition 129.

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

Proposition 131

$\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:{\mathrm{𝐍𝐀𝐑𝐂}}_{1}+{\mathrm{𝐍𝐀𝐑𝐂}}_{2}={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-1$

Proof 129 Holds since each arc of the initial graph belongs to one of the two final graphs and since the initial graph has ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}-1$ arcs.

${\mathrm{𝐍𝐂𝐂}}_{1}$, ${\mathrm{𝐍𝐂𝐂}}_{2}$

Proposition 132

$\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:|{\mathrm{𝐍𝐂𝐂}}_{1}-{\mathrm{𝐍𝐂𝐂}}_{2}|\le 1$

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚕𝚘𝚘𝚙𝚜}_\mathrm{𝚊𝚛𝚎}_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}:|{\mathrm{𝐍𝐂𝐂}}_{1}-{\mathrm{𝐍𝐂𝐂}}_{2}|\le 1$

Proof 130 Holds because the two initial graphs correspond to a path and because consecutive connected components do not come from the same graph constraint.

Proposition 133

$\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\wedge \mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:{\mathrm{𝐍𝐂𝐂}}_{1}+{\mathrm{𝐍𝐂𝐂}}_{2}<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}$

Proof 131 Holds because the initial graph is a path.

${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{1}$, ${\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{2}$

Proposition 134

$\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}:{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{1}+{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{2}={\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}_{\mathrm{𝙸𝙽𝙸𝚃𝙸𝙰𝙻}}$

Proof 132 By definition of $\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ each vertex of the initial graph belongs to one of the two final graphs (but not to both).