Proposition 125

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.

Proposition 126

Proof 124 Similar to Proposition 125.

Proposition 127

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.

Proposition 128

Proof 126 Similar to Proposition 127.

Proposition 129

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.

Proposition 130

Proof 128 Similar to Proposition 129.

Proposition 131

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.

Proposition 132

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

Proof 131 Holds because the initial graph is a path.

Proposition 134

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