4.3.4.7. three parameters/two final graphs

πŒπ€π—_𝐍𝐂𝐂 1 , 𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐌𝐈𝐍_𝐍𝐂𝐂 2

Proposition 135

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(3,𝐌𝐈𝐍_𝐍𝐂𝐂 1 +1,πŒπ€π—_𝐍𝐂𝐂 1 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 2 )-2>𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» β‡’πŒπˆπ_𝐍𝐂𝐂 1 =πŒπ€π—_𝐍𝐂𝐂 1

Proof 133 The quantity max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(3,𝐌𝐈𝐍_𝐍𝐂𝐂 1 +1,πŒπ€π—_𝐍𝐂𝐂 1 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 2 )-2 corresponds to the minimum number of variables needed for building two non -empty connected components of respective size 𝐌𝐈𝐍_𝐍𝐂𝐂 1 and πŒπ€π—_𝐍𝐂𝐂 1 such that πŒπ€π—_𝐍𝐂𝐂 1 is strictly greater than 𝐌𝐈𝐍_𝐍𝐂𝐂 1 . If this quantity is greater than the total number of variables we have that 𝐌𝐈𝐍_𝐍𝐂𝐂 1 =πŒπ€π—_𝐍𝐂𝐂 1 .

Proposition 136

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš:max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 +1,πŒπ€π—_𝐍𝐂𝐂 1 )+max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 )>𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» β‡’πŒπˆπ_𝐍𝐂𝐂 1 =πŒπ€π—_𝐍𝐂𝐂 1

Proof 134 The quantity max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 +1,πŒπ€π—_𝐍𝐂𝐂 1 )+max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 ) corresponds to the minimum number of variables needed for building two non -empty connected components of respective size 𝐌𝐈𝐍_𝐍𝐂𝐂 1 and πŒπ€π—_𝐍𝐂𝐂 1 such that πŒπ€π—_𝐍𝐂𝐂 1 is strictly greater than 𝐌𝐈𝐍_𝐍𝐂𝐂 1 . If this quantity is greater than the total number of variables we have that 𝐌𝐈𝐍_𝐍𝐂𝐂 1 =πŒπ€π—_𝐍𝐂𝐂 1 .

Proposition 137

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš:𝐌𝐈𝐍_𝐍𝐂𝐂 2 βˆ‰[max(𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 1 -𝐌𝐈𝐍_𝐍𝐂𝐂 1 +1, 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 1 +2 2), 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 1 -1]

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+πŒπ€π—_𝐍𝐂𝐂 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.

πŒπ€π—_𝐍𝐂𝐂 2 , 𝐌𝐈𝐍_𝐍𝐂𝐂 2 , 𝐌𝐈𝐍_𝐍𝐂𝐂 1

Proposition 138

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 2 )+max(3,𝐌𝐈𝐍_𝐍𝐂𝐂 2 +1,πŒπ€π—_𝐍𝐂𝐂 2 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )-2>𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» β‡’πŒπˆπ_𝐍𝐂𝐂 2 =πŒπ€π—_𝐍𝐂𝐂 2

Proof 136 Similar to PropositionΒ 135.

Proposition 139

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš:max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 2 )+max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 2 +1,πŒπ€π—_𝐍𝐂𝐂 2 )+max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )>𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» β‡’πŒπˆπ_𝐍𝐂𝐂 2 =πŒπ€π—_𝐍𝐂𝐂 2

Proof 137 Similar to PropositionΒ 136.

Proposition 140

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πš•πš˜πš˜πš™πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš:𝐌𝐈𝐍_𝐍𝐂𝐂 1 βˆ‰[max(𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 2 -𝐌𝐈𝐍_𝐍𝐂𝐂 2 +1, 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 2 +2 2), 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -πŒπ€π—_𝐍𝐂𝐂 2 -1]

Proof 138 Similar to PropositionΒ 137.

πŒπ€π—_𝐍𝐂𝐂 1 , 𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2

Proposition 141

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—:𝐌𝐈𝐍_𝐍𝐂𝐂 1 =πŒπ€π—_𝐍𝐂𝐂 1 ∧𝐌𝐈𝐍_𝐍𝐂𝐂 1 mod 2=0β‡’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 mod 2=𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» mod 2

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

πŒπ€π—_𝐍𝐂𝐂 2 , 𝐌𝐈𝐍_𝐍𝐂𝐂 2 , 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 1

Proposition 142

πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—:𝐌𝐈𝐍_𝐍𝐂𝐂 2 =πŒπ€π—_𝐍𝐂𝐂 2 ∧𝐌𝐈𝐍_𝐍𝐂𝐂 2 mod 2=0β‡’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 1 mod 2=𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» mod 2

Proof 140 Similar to PropositionΒ 141.

𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐍𝐀𝐑𝐂 2 , 𝐍𝐂𝐂 1

Proposition 143

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§ππ•π„π‘π“π„π— π™Έπ™½π™Έπšƒπ™Έπ™°π™» >0: 𝐍𝐂𝐂 1 =1β‡”πŒπˆπ_𝐍𝐂𝐂 1 +𝐍𝐀𝐑𝐂 2 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 141 When 𝐌𝐈𝐍_𝐍𝐂𝐂 1 +𝐍𝐀𝐑𝐂 2 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» there is no more room for an extra connected component for the first final graph.

𝐌𝐈𝐍_𝐍𝐂𝐂 1 , 𝐍𝐀𝐑𝐂 2 , 𝐍𝐂𝐂 1

Proposition 144

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§ππ•π„π‘π“π„π— π™Έπ™½π™Έπšƒπ™Έπ™°π™» >0: 𝐍𝐂𝐂 2 =1β‡”πŒπˆπ_𝐍𝐂𝐂 2 +𝐍𝐀𝐑𝐂 1 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™»

Proof 142 Similar to PropositionΒ 143.