4.3.4.8. four parameters/two final graphs

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

Proposition 145

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

Proof 143 The quantity max(2,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(2,πŒπ€π—_𝐍𝐂𝐂 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 . If this quantity is greater than the total number of variables we have that 𝐍𝐂𝐂 1 ≀1.

Proposition 146

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

Proof 144 The quantity max(1,𝐌𝐈𝐍_𝐍𝐂𝐂 1 )+max(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 . If this quantity is greater than the total number of variables we have that 𝐍𝐂𝐂 1 ≀1.

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

Proposition 147

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

Proof 145 Similar to PropositionΒ 145.

Proposition 148

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

Proof 146 Similar to PropositionΒ 146.

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

Proposition 149

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

Proof 147 First, note that, when 𝐍𝐂𝐂 2 >1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂 2 ≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 2. Second, note that, when 𝐍𝐂𝐂 2 ≀1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂 2 β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» -𝐌𝐈𝐍_𝐍𝐂𝐂 1 -πŒπ€π—_𝐍𝐂𝐂 1 . Since 𝐍𝐂𝐂 2 has to have at least one value the result follows.

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

Proposition 150

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

Proof 148 Similar to PropositionΒ 149.