4.3.4.10. six parameters/two final graphs

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

Proposition 165

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§ππ•π„π‘π“π„π— π™Έπ™½π™Έπšƒπ™Έπ™°π™» >0: α·𝐌𝐈𝐍_𝐍𝐂𝐂 1 +πŒπ€π—_𝐍𝐂𝐂 1 + β·𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2 ≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» +𝐍𝐂𝐂 1 +𝐍𝐂𝐂 2 -1, πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐂𝐂 1 -1),β€’ Ξ²=max(0,𝐍𝐂𝐂 2 -1).

Proof 163 Let CC(G 1 )={CC a 1 :a∈[𝐍𝐂𝐂1]} and CC(G 2 )={CC a 2 :a∈[𝐍𝐂𝐂2]} be respectively the set of connected components of the first and the second final graphs. Since the initial graph is a path, and since each arc of the initial graph belongs to the first or to the second final graphs (but not to both), there exists (A i ) i∈[𝐍𝐂𝐂 1 +𝐍𝐂𝐂 2 ] and there exists j∈[2] such that A i ∈CC(G 1+(j mod 2) ), for i mod 2=0 and A i ∈CC(G 1+((j+1) mod 2) ) for i mod 2=1 and A i ∩A i+1 β‰ βˆ… for i∈[𝐍𝐂𝐂 1 +𝐍𝐂𝐂 2 -1].

By inclusion -exclusion principle, since A i ∩A j =βˆ… whenever jβ‰ i+1, we obtain 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» =Ξ£ a∈[𝐍𝐂𝐂1] |CC a 1 |+Ξ£ a∈[𝐍𝐂𝐂2] |CC a 2 |-Ξ£ i∈[𝐍𝐂𝐂1+𝐍𝐂𝐂2-1] |A i ∩A i+1 |. Since |A i ∩A i+1 | is equal to 1 for every well defined i, we obtain Ξ£ a∈[𝐍𝐂𝐂1] |CC a 1 |+Ξ£ a∈[𝐍𝐂𝐂2] |CC a 2 |=𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» +𝐍𝐂𝐂1+𝐍𝐂𝐂2-1.

Since α·𝐌𝐈𝐍_𝐍𝐂𝐂 1 +πŒπ€π—_𝐍𝐂𝐂 1 +β·𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2 ≀Σ a∈[𝐍𝐂𝐂1] |CC a 1 |+Ξ£ a∈[𝐍𝐂𝐂2] |CC a 2 | the result follows.

Proposition 166

πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—βˆ§πšπ«πœ_𝐠𝐞𝐧=π‘ƒπ΄π‘‡π»βˆ§ππ•π„π‘π“π„π— π™Έπ™½π™Έπšƒπ™Έπ™°π™» >0: Ξ±Β·πŒπ€π—_𝐍𝐂𝐂 1 +𝐌𝐈𝐍_𝐍𝐂𝐂 1 + Ξ²Β·πŒπ€π—_𝐍𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐂𝐂 2 β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 π™Έπ™½π™Έπšƒπ™Έπ™°π™» +𝐍𝐂𝐂 1 +𝐍𝐂𝐂 2 -1, πš πš’πšπš‘: β€’ Ξ±=max(0,𝐍𝐂𝐂 1 -1),β€’ Ξ²=max(0,𝐍𝐂𝐂 2 -1).

Proof 164 Similar to PropositionΒ 165.