4.3.4.3. three parameters/one final graph

Proposition 68

𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒ 𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂-2+(𝐌𝐈𝐍_𝐍𝐂𝐂=1)

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒ 𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2

Proof 68 (89) n-1 arcs are needed to connect n (n>1) vertices that all belong to a given connected component. Since we have two connected components, which respectively have 𝐌𝐈𝐍_𝐍𝐂𝐂 and πŒπ€π—_𝐍𝐂𝐂 vertices, this leads to the previous inequality. When 𝐌𝐈𝐍_𝐍𝐂𝐂 is equal to one we need an extra arc.

Proposition 69

𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒𝐍𝐂𝐂β‰₯2

Proof 69 If 𝐌𝐈𝐍_𝐍𝐂𝐂 and πŒπ€π—_𝐍𝐂𝐂 are different then they correspond for sure to at least two distinct connected components.

Proposition 70

𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂

Proof 70 Since we have at least two distinct connected components, which respectively have 𝐌𝐈𝐍_𝐍𝐂𝐂 and πŒπ€π—_𝐍𝐂𝐂 vertices, this leads to the previous inequality.

Proposition 71

πŒπ€π—_𝐍𝐂𝐂≀max(𝐌𝐈𝐍_𝐍𝐂𝐂,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-max(1,𝐌𝐈𝐍_𝐍𝐂𝐂))

Proof 71 On the one hand, if 𝐍𝐂𝐂≀1, we have that πŒπ€π—_ππ‚π‚β‰€πŒπˆπ_𝐍𝐂𝐂. On the other hand, if 𝐍𝐂𝐂>1, we have that 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯max(1,𝐌𝐈𝐍_𝐍𝐂𝐂)+πŒπ€π—_𝐍𝐂𝐂 (i.e.,Β πŒπ€π—_𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-max(1,𝐌𝐈𝐍_𝐍𝐂𝐂)). The result is obtained by taking the maximum value of the right-hand sides of the two inequalities.

Proposition 72

𝐌𝐈𝐍_ππ‚π‚βˆ‰ππ•π„π‘π“π„π—-max(1,πŒπ€π—_𝐍𝐂𝐂)+1,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1

Proof 72 On the one hand, if 𝐍𝐂𝐂≀1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗. On the other hand, if 𝐍𝐂𝐂>1, we have that 𝐌𝐈𝐍_𝐍𝐂𝐂+max(1,πŒπ€π—_𝐍𝐂𝐂)≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 (i.e., 𝐌𝐈𝐍_𝐍𝐂𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-max(1,πŒπ€π—_𝐍𝐂𝐂)). The result follows.

Proposition 73

ππ•π„π‘π“π„π—βˆ‰πŒπˆπ_𝐍𝐂𝐂+1,𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂-1

Proof 73 On the one hand, if 𝐍𝐂𝐂≀1, we have that ππ•π„π‘π“π„π—β‰€πŒπˆπ_𝐍𝐂𝐂. On the other hand, if 𝐍𝐂𝐂>1, we have that 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂. Since 𝐌𝐈𝐍_ππ‚π‚β‰€πŒπˆπ_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂 the result follows.

Proposition 74

πš’πš 𝐌𝐈𝐍_𝐍𝐂𝐂 Β―>0πšπš‘πšŽπš— k 𝑖𝑛𝑓 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Μ²+𝐌𝐈𝐍_𝐍𝐂𝐂 Β― 𝐌𝐈𝐍_𝐍𝐂𝐂 Β― πšŽπš•πšœπšŽ k 𝑖𝑛𝑓 =1
πš’πš πŒπ€π—_𝐍𝐂𝐂 Μ²>0πšπš‘πšŽπš— k 𝑠𝑒𝑝 1 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―-1 πŒπ€π—_𝐍𝐂𝐂 Μ² πšŽπš•πšœπšŽ k 𝑠𝑒𝑝 1 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―
πš’πš πŒπ€π—_𝐍𝐂𝐂 Μ²<𝐌𝐈𝐍_𝐍𝐂𝐂 Β―πšπš‘πšŽπš— k 𝑠𝑒𝑝 2 =𝐌𝐈𝐍_𝐍𝐂𝐂 Β―-2 πŒπ€π—_𝐍𝐂𝐂 Μ²-𝐌𝐈𝐍_𝐍𝐂𝐂 Β― πšŽπš•πšœπšŽ k 𝑠𝑒𝑝 2 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―
k 𝑠𝑒𝑝 =min(k 𝑠𝑒𝑝 1 ,k 𝑠𝑒𝑝 2 )
βˆ€k∈[k 𝑖𝑛𝑓 ,k 𝑠𝑒𝑝 ]:ππ•π„π‘π“π„π—βˆ‰kΒ·πŒπ€π—_𝐍𝐂𝐂+1,(k+1)·𝐌𝐈𝐍_𝐍𝐂𝐂-1

Proof 74 We make the proof for kβˆˆβ„• (the interval [k 𝑖𝑛𝑓 ,k 𝑠𝑒𝑝 ] is only used for restricting the number of intervals to check). We have that ππ•π„π‘π“π„π—βˆˆ[k·𝐌𝐈𝐍_𝐍𝐂𝐂,kΒ·πŒπ€π—_𝐍𝐂𝐂]. A forbidden interval [kΒ·πŒπ€π—_𝐍𝐂𝐂+1,(k+1)·𝐌𝐈𝐍_𝐍𝐂𝐂-1] corresponds to an interval between the end of interval [k·𝐌𝐈𝐍_𝐍𝐂𝐂,kΒ·πŒπ€π—_𝐍𝐂𝐂] and the start of the next interval [(k+1)·𝐌𝐈𝐍_𝐍𝐂𝐂,(k+1)Β·πŒπ€π—_𝐍𝐂𝐂]. Since all intervals [i·𝐌𝐈𝐍_𝐍𝐂𝐂,iΒ·πŒπ€π—_𝐍𝐂𝐂] (i<k) end before kΒ·πŒπ€π—_𝐍𝐂𝐂 and since all intervals [j·𝐌𝐈𝐍_𝐍𝐂𝐂,jΒ·πŒπ€π—_𝐍𝐂𝐂] (j>k) start after (k+1)·𝐌𝐈𝐍_𝐍𝐂𝐂, they do not use any value in [kΒ·πŒπ€π—_𝐍𝐂𝐂+1,(k+1)·𝐌𝐈𝐍_𝐍𝐂𝐂-1].

Proposition 75

ππ€π‘π‚β‰€ππ‚π‚Β·πŒπ€π—_𝐍𝐂𝐂 2

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂·(πŒπ€π—_𝐍𝐂𝐂-1)

Proof 75 On the one hand, (97) holds since the maximum number of arcs is achieved by taking 𝐍𝐂𝐂 connected components where each connected component is a clique involving πŒπ€π—_𝐍𝐂𝐂 vertices. On the other hand, (98) holds since a tree of n vertices has n-1 arcs.

Proposition 76

𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐂𝐂+𝐍𝐂𝐂-2

Proof 76 The minimum number of arcs is achieved by taking one connected component with πŒπ€π—_𝐍𝐂𝐂 vertices and πŒπ€π—_𝐍𝐂𝐂-1 arcs as well as 𝐍𝐂𝐂-1 connected components with a single vertex and a loop.

Proposition 77

ππ€π‘π‚β‰€πŒπ€π—_𝐍𝐂𝐂 2 ·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 max(1,πŒπ€π—_𝐍𝐂𝐂)+(𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod max(1,πŒπ€π—_𝐍𝐂𝐂)) 2

Figure 4.3.1. Illustration of PropositionΒ 77. A graph that achieves the maximum number of arcs according to the size of the largest connected component as well as to a fixed number of vertices (π™Όπ™°πš‡_𝙽𝙲𝙲=3,π™½πš…π™΄πšπšƒπ™΄πš‡=11,π™½π™°πšπ™²=3 2 Β·11 max(1,3)+(11 mod max(1,3)) 2 =31)
ctrs/preface-218-tikz

Proof 77 If πŒπ€π—_𝐍𝐂𝐂=0 we get 𝐍𝐀𝐑𝐂≀0 which holds since the set of vertices is empty. We now assume that πŒπ€π—_𝐍𝐂𝐂>0. We first begin with the following claim:

let G be a graph such that V(G)-𝐍𝐂𝐂(G,πŒπ€π—_𝐍𝐂𝐂(G))*πŒπ€π—_𝐍𝐂𝐂(G)β‰₯πŒπ€π—_𝐍𝐂𝐂(G), then there exists a graph G ' such that V(G ' )=V(G), πŒπ€π—_𝐍𝐂𝐂(G ' )=πŒπ€π—_𝐍𝐂𝐂(G), 𝐍𝐂𝐂(G ' ,πŒπ€π—_𝐍𝐂𝐂(G ' ))=𝐍𝐂𝐂(G,πŒπ€π—_𝐍𝐂𝐂(G))+1 and |E(G)|≀|E(G ' )|.

Proof of the claim

Let (C i ) i∈[n] be the connected components of G on less than πŒπ€π—_𝐍𝐂𝐂(G) vertices and such that |C i |β‰₯|C i+1 |. By hypothesis there exists k≀n such that |⋃ i=1 k-1 C i |<πŒπ€π—_𝐍𝐂𝐂(G) and |⋃ i=1 k C i |β‰₯πŒπ€π—_𝐍𝐂𝐂(G).

  • Either |⋃ i=1 k C i |=πŒπ€π—_𝐍𝐂𝐂(G), and then with G ' such that G ' restricted to the ⋃ i=1 k C i be a complete graph and G ' restricted to V(G)-⋃ i=1 k C i being exactly G restricted to V(G)-⋃ i=1 k C i we obtain the claim.

  • Or |⋃ i=1 k C i |>πŒπ€π—_𝐍𝐂𝐂(G). Then C k =C k 1 ⊎C k 2 such that |(⋃ i=1 k-1 C i )βˆͺC k 1 |=πŒπ€π—_𝐍𝐂𝐂(G) and |C k 2 |<|C 1 | (notice that kβ‰₯2). Then with G ' such that G ' restricted to (⋃ i=1 k-1 C i )βˆͺC k 1 is a complete graph and G ' restricted to V(G)-((⋃ i=1 k-1 C i )βˆͺC k 1 ) is exactly G restricted to V(G)-((⋃ i=1 k-1 C i )βˆͺC k 1 ) we obtain the claim.

End of proof of the claim

We prove by induction on r(G)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G) πŒπ€π—_𝐍𝐂𝐂(G)-𝐍𝐂𝐂(G,πŒπ€π—_𝐍𝐂𝐂(G)), where G is any graph. For r(G)=0 the result holds (see Prop 44). Otherwise, since r(G)>0 we have that V(G)-𝐍𝐂𝐂(G,πŒπ€π—_𝐍𝐂𝐂(G))*πŒπ€π—_𝐍𝐂𝐂(G)β‰₯πŒπ€π—_𝐍𝐂𝐂(G), by the previous claim there exists G ' with the same number of vertices and the same number of vertices in the largest connected component, such that r(G ' )=r(G)-1. Consequently the result holds by induction.

Proposition 78

𝐍𝐀𝐑𝐂β‰₯πŒπ€π—_𝐍𝐂𝐂-1+𝐍𝐕𝐄𝐑𝐓𝐄𝐗-πŒπ€π—_𝐍𝐂𝐂+1 2

Proof 78 Let G be a graph, let X be a maximal size connected component of G, then we have G=G[X]βŠ•G[V(G)-X]. On the one hand, as G[X] is connected, by setting 𝐍𝐂𝐂=1 inΒ 143 of PropositionΒ 99, we have |E(G[X])β‰₯|X|-1, on the other hand, by PropositionΒ 52, |E(G[V(G)-X])|β‰₯|V(G)-X| 2. Thus the result follows.

Proposition 79

ππ’πˆππŠβ‰€ππ‚π‚Β·max(0,πŒπ€π—_𝐍𝐂𝐂-1)

Proof 79 Since a connected component contains at most πŒπ€π—_𝐍𝐂𝐂 vertices and since it does not contain any isolated vertex a connected component involves at most πŒπ€π—_𝐍𝐂𝐂-1 sinks. Thus the result follows.

Proposition 80

ππ’πŽπ”π‘π‚π„β‰€ππ‚π‚Β·max(0,πŒπ€π—_𝐍𝐂𝐂-1)

Proof 80 Similar to PropositionΒ 79.

Proposition 81

ππ•π„π‘π“π„π—β‰€ππ‚π‚Β·πŒπ€π—_𝐍𝐂𝐂

Proof 81 The number of vertices is less than or equal to the number of connected components multiplied by the largest number of vertices in a connected component.

Proposition 82

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐂𝐂+max(0,𝐍𝐂𝐂-1)

πš—πš˜ πš•πš˜πš˜πš™:𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐂𝐂+max(0,2·𝐍𝐂𝐂-2)

Proof 82 (105) The minimum number of vertices according to a fixed number of connected components 𝐍𝐂𝐂 such that one of the connected components contains πŒπ€π—_𝐍𝐂𝐂 vertices is obtained as follows: we get πŒπ€π—_𝐍𝐂𝐂 vertices from the connected component involving πŒπ€π—_𝐍𝐂𝐂 vertices and one vertex for each remaining connected component.

Proposition 83

𝐌𝐈𝐍_ππ’π‚π‚β‰ πŒπ€π—_𝐍𝐒𝐂𝐂⇒𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂+πŒπ€π—_𝐍𝐒𝐂𝐂

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐌𝐈𝐍_ππ’π‚π‚β‰ πŒπ€π—_𝐍𝐒𝐂𝐂⇒ 𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 2 +πŒπ€π—_𝐍𝐒𝐂𝐂 2

Proof 83 (107) In a strongly connected component at least one arc has to leave each arc. Since we have two strongly connected components, which respectively have 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 and πŒπ€π—_𝐍𝐒𝐂𝐂 vertices, this leads to the previous inequality.

Proposition 84

𝐌𝐈𝐍_ππ’π‚π‚β‰ πŒπ€π—_𝐍𝐒𝐂𝐂⇒𝐍𝐒𝐂𝐂β‰₯2

Proposition 85

𝐌𝐈𝐍_ππ’π‚π‚β‰ πŒπ€π—_𝐍𝐒𝐂𝐂⇒𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯𝐌𝐈𝐍_𝐍𝐒𝐂𝐂+πŒπ€π—_𝐍𝐒𝐂𝐂

Proof 85 Since we have at least two distinct strongly connected components, which respectively have 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 and πŒπ€π—_𝐍𝐒𝐂𝐂 vertices, this leads to the previous inequality.

Proposition 86

πš’πš 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β―>0πšπš‘πšŽπš— k 𝑖𝑛𝑓 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Μ²+𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β― 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β― πšŽπš•πšœπšŽ k 𝑖𝑛𝑓 =1
πš’πš πŒπ€π—_𝐍𝐒𝐂𝐂 Μ²>0πšπš‘πšŽπš— k 𝑠𝑒𝑝 1 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―-1 πŒπ€π—_𝐍𝐒𝐂𝐂 Μ² πšŽπš•πšœπšŽ k 𝑠𝑒𝑝 1 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―
πš’πš πŒπ€π—_𝐍𝐒𝐂𝐂 Μ²<𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β―πšπš‘πšŽπš— k 𝑠𝑒𝑝 2 =𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β―-2 πŒπ€π—_𝐍𝐒𝐂𝐂 Μ²-𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 Β― πšŽπš•πšœπšŽ k 𝑠𝑒𝑝 2 =𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―
k 𝑠𝑒𝑝 =min(k 𝑠𝑒𝑝 1 ,k 𝑠𝑒𝑝 2 )
βˆ€k∈[k 𝑖𝑛𝑓 ,k 𝑠𝑒𝑝 ]:ππ•π„π‘π“π„π—βˆ‰kΒ·πŒπ€π—_𝐍𝐒𝐂𝐂+1,(k+1)·𝐌𝐈𝐍_𝐍𝐒𝐂𝐂-1

Proof 86 Similar to PropositionΒ 74.

Proposition 87

ππ•π„π‘π“π„π—β‰€ππ‚π‚Β·πŒπ€π—_𝐍𝐒𝐂𝐂

Proof 87 The largest number of vertices is obtained by putting within each connected component the number of vertices of the largest strongly connected component.

Proposition 88

ππ•π„π‘π“π„π—β‰€ππ’π‚π‚Β·πŒπ€π—_𝐍𝐒𝐂𝐂

Proof 88 Since each strongly connected component contains at most πŒπ€π—_𝐍𝐒𝐂𝐂 vertices the total number of vertices is less than or equal to ππ’π‚π‚Β·πŒπ€π—_𝐍𝐒𝐂𝐂.

Proposition 89

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐒𝐂𝐂+max(0,𝐍𝐒𝐂𝐂-1)

πš—πš˜ πš•πš˜πš˜πš™:𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πŒπ€π—_𝐍𝐒𝐂𝐂+max(0,2·𝐍𝐒𝐂𝐂-2)

Proof 89 (114) The minimum number of vertices according to a fixed number of strongly connected components 𝐍𝐒𝐂𝐂 such that one of them contains πŒπ€π—_𝐍𝐒𝐂𝐂 vertices is equal to πŒπ€π—_𝐍𝐒𝐂𝐂+max(0,𝐍𝐒𝐂𝐂-1).

Proposition 90

ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂 2 +(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2Β·(𝐌𝐈𝐍_𝐍𝐂𝐂<𝐍𝐕𝐄𝐑𝐓𝐄𝐗)

𝐚𝐫𝐜_𝐠𝐞𝐧=𝐢𝐻𝐴𝐼𝑁:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2Β·(𝐌𝐈𝐍_𝐍𝐂𝐂<𝐍𝐕𝐄𝐑𝐓𝐄𝐗)

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(≀):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂+1) 2+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂+1) 2+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(<):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂-1) 2+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(>):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂-1) 2+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂 2 -𝐌𝐈𝐍_𝐍𝐂𝐂+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂) 2 -(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂)

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπ‘ŒπΆπΏπΈ:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-4Β·(𝐌𝐈𝐍_𝐍𝐂𝐂<𝐍𝐕𝐄𝐑𝐓𝐄𝐗)

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂≀max(0,𝐌𝐈𝐍_𝐍𝐂𝐂-1)+ max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂-1)

Proof 90 (116) The maximum number of vertices according to a fixed number of vertices 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 and to the fact that there is a connected component with 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices is obtained by:

  • Building a connected component with 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices and creating an arc between each pair of vertices.

  • Building a connected component with all the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐂𝐂 remaining vertices and creating an arc between each pair of vertices.

Proposition 91

𝐌𝐈𝐍_𝐍𝐂𝐂>1β‡’ 𝐍𝐀𝐑𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐌𝐈𝐍_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂-1)+𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐌𝐈𝐍_𝐍𝐂𝐂

Proof 91 Achieving the minimum number of arcs with a fixed number of vertices and with a minimum number of vertices greater than or equal to one in each connected component is achieved in the following way:

  • Since the minimum number of arcs of a connected component of n vertices is n-1, splitting a connected component into k parts that all have more than one vertex saves k-1 arcs. Therefore we build a maximum number of connected components. Since each connected component has at least 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices we get 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐌𝐈𝐍_𝐍𝐂𝐂 connected components.

  • Since we cannot build a connected component with the rest of the vertices (i.e., 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices left) we have to incorporate them in the previous connected components and this costs one arc for each vertex.

When 𝐌𝐈𝐍_𝐍𝐂𝐂=1, note that PropositionΒ 52 provides a lower bound on the number of arcs.

Proposition 92

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯ππ‚π‚Β·πŒπˆπ_𝐍𝐂𝐂

Proof 92 The smallest number of vertices is obtained by taking all connected components to their minimum number of vertices 𝐌𝐈𝐍_𝐍𝐂𝐂.

Proposition 93

𝐍𝐕𝐄𝐑𝐓𝐄𝐗>𝐌𝐈𝐍_𝐍𝐂𝐂⇒𝐍𝐂𝐂β‰₯2

Proof 93 If all vertices do not fit within the smallest connected component then we have at least two connected components.

Proposition 94

𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 +𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 2 -ππ•π„π‘π“π„π—Β·πŒπˆπ_𝐍𝐒𝐂𝐂

Proof 94 Achieving the maximum number of arcs, provided that we have at least one strongly connected component with 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 vertices, is done by:

  • Building a first strongly connected component π’ž 1 with 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 vertices and adding an arc between each pair of vertices of π’ž 1 .

  • Building a second strongly connected component π’ž 2 with 𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 vertices and adding an arc between each pair of vertices of π’ž 2 .

Finally, we add an arc from every vertex of π’ž 1 to every vertex of π’ž 2 . This leads to a total number of arcs of 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 2 +(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐒𝐂𝐂) 2 +𝐌𝐈𝐍_𝐍𝐒𝐂𝐂·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐌𝐈𝐍_𝐍𝐒𝐂𝐂).

Proposition 95

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯ππ‚π‚Β·πŒπˆπ_𝐍𝐒𝐂𝐂

Proof 95 The smallest number of vertices is obtained by putting within each connected component the number of vertices of the smallest strongly connected component.

Proposition 96

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯ππ’π‚π‚Β·πŒπˆπ_𝐍𝐒𝐂𝐂

Proof 96 Since each strongly connected component contains at least 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 vertices the total number of vertices is greater than or equal to ππ’π‚π‚Β·πŒπˆπ_𝐍𝐒𝐂𝐂.

Proposition 97

𝐍𝐕𝐄𝐑𝐓𝐄𝐗>𝐌𝐈𝐍_𝐍𝐒𝐂𝐂⇒𝐍𝐒𝐂𝐂β‰₯2

Proof 97 If all vertices do not fit within the smallest strongly connected component then we have at least two strongly connected components.

Proposition 98

𝐍𝐀𝐑𝐂≀(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1) 2 +𝐍𝐂𝐂-1

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡:𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1-(𝐍𝐂𝐂≠1)

𝐚𝐫𝐜_𝐠𝐞𝐧=𝐢𝐻𝐴𝐼𝑁:𝐍𝐀𝐑𝐂≀2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2·𝐍𝐂𝐂

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(≀):𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂-1+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+2) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯):𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂-1+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+2) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(<):𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂-1+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(>):𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂-1+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):𝐍𝐀𝐑𝐂≀max(0,𝐍𝐂𝐂-1)+ (𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1) 2 -(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπ‘ŒπΆπΏπΈ:𝐍𝐀𝐑𝐂≀2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2·𝐍𝐂𝐂+2Β·(𝐍𝐂𝐂=1)

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂=𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂

Figure 4.3.2. Illustration of PropositionΒ 98. A graph that achieves the maximum number of arcs according to a fixed number of connected components as well as to a fixed number of vertices (𝙽𝙲𝙲=5,π™½πš…π™΄πšπšƒπ™΄πš‡=7,π™½π™°πšπ™²=(7-5+1) 2 +5-1=13)
ctrs/preface-219-tikz

Proof 98 (133) We proceed by induction on T(G)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-|X|-(𝐍𝐂𝐂(G)-1), where X is any connected component of G of maximum cardinality. For T(G)=0 then either 𝐍𝐂𝐂(G)=1 and thus the formula is clearly true, or all the connected components of G, but possibly X, are reduced to one element. Since isolated vertices are not allowed, the formula holds.

Assume that T(G)β‰₯1. Then there exists Y, a connected component of G distinct from X, with more than one vertex. Let y∈Y and let G ' be the graph such that V(G ' )=V(G) and E(G ' ) is defined by:

  • For all Z connected components of G distinct from X and Y we have G ' [Z]=G[Z].

  • With X ' =Xβˆͺ{y} and Y ' =Y-{y}, we have G ' [Y ' ]=G[Y ' ] and E(G ' [X ' ])=E(G[X])βˆͺ(⋃ x∈X ' {(x,y),(y,x)}).

Clearly |E(G ' )|-|E(G)|β‰₯2Β·|X|+1-(2Β·|Y|-1) and since X is of maximal cardinality the difference is strictly positive. Now as 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G), 𝐍𝐂𝐂(G ' )=𝐍𝐂𝐂(G) and as T(G ' )=T(G)-1 the result holds by induction hypothesis.

Proposition 99

𝐍𝐀𝐑𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯(𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐍𝐂𝐂)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐂𝐂+1 2 +(𝐍𝐂𝐂-𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐍𝐂𝐂)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐂𝐂 2

Proof 99 (143) By induction of the number of vertices. The formula holds for one vertex. Let G a graph with n+1 vertices (nβ‰₯1). First assume there exists x in G such that G-x has the same number of connected components than G. Since 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐀𝐑𝐂(G-x)+1, and by induction hypothesis 𝐍𝐀𝐑𝐂(G-x)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G-x)-𝐍𝐂𝐂(G-x) the result holds. Otherwise all connected components of G are reduced to one vertex and the formula holds.

Proposition 100

𝐍𝐀𝐑𝐂≀(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐒𝐂𝐂+1)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗+𝐍𝐒𝐂𝐂·(𝐍𝐒𝐂𝐂-1) 2

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐀𝐑𝐂≀𝐍𝐒𝐂𝐂-1+(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐒𝐂𝐂+1) 2

Figure 4.3.3. Illustration of PropositionΒ 100(145). A graph that achieves the maximum number of arcs according to a fixed number of strongly connected components as well as to a fixed number of vertices (π™½πš‚π™²π™²=5,π™½πš…π™΄πšπšƒπ™΄πš‡=6,π™½π™°πšπ™²=(6-5+1)Β·6+5Β·(5-1) 2=22)
ctrs/preface-220-tikz

Proof 100 For provingΒ 145, it is easier to rewrite the formula as 𝐍𝐀𝐑𝐂≀(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-(𝐍𝐒𝐂𝐂-1)) 2 +(𝐍𝐂𝐂-1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-(𝐍𝐒𝐂𝐂-1))+𝐍𝐒𝐂𝐂·(𝐍𝐒𝐂𝐂-1) 2. We proceed by induction on T(G)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-|X|-(𝐍𝐒𝐂𝐂(G)-1), where X is any strongly connected component of G of maximum cardinality.

For T(G)=0 then either 𝐍𝐒𝐂𝐂(G)=1 and thus the formula is clearly true, or all the strongly connected components of G, but possibly X, are reduced to one element. Since the maximum number of arcs in a directed acyclic graph of n vertices is nΒ·(n+1) 2, and as the subgraph of G induced by all the strongly connected components of G excepted X is acyclic, the formula clearly holds.

Assume that T(G)β‰₯1, let (X i ) i∈I be the family of strongly connected components of G, and let G r be the reduced graph of G induced by (X i ) i∈I (that is V(G r )=I and βˆ€i 1 ,i 2 ∈I, (i 1 ,i 2 )∈E(G r ) if and only if βˆƒx 1 ∈X i 1 , βˆƒx 2 ∈X i 2 such that (x 1 ,x 2 )∈E). Consider G ' such that V(G ' )=V(G) and E(G ' ) is defined by:

  • For all strongly connected components Z of G we have G ' [Z]=G[Z].

  • For Οƒ be any topological sort of G r , βˆ€x i ∈X i , βˆ€x j ∈X j , (x i ,x j )∈E(G ' ) whenever i is less than j with respect to Οƒ.

Notice that G ' satisfies the following properties: T(G ' )=T(G), V(G ' )=V(G), 𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G), E(G)βŠ†E(G ' ), (X i ) i∈I is still the family of strongly connected components of G ' , and moreover, for every i∈I and every x i ∈X i we have that x i is connected to any vertex outside X i , that is the number of arcs incident to x i and incident to vertices outside X i is exactly |V(G ' )|-|X i |.

Now, as T(G ' )β‰₯1, there exists Y, a strongly connected component of G ' distinct from X, with more than one vertex. Let y∈Y and let G '' be the graph such that V(G '' )=V(G ' ) and E(G '' ) is defined by:

  • G '' [V(G)-{y}]=G ' [V(G)-{y}].

  • With X ' =Xβˆͺ{y}, we have G '' [Y ' ]=G ' [Y ' ] and E(G '' [X ' ])=E(G ' [X])βˆͺ(⋃ x∈X ' {(x,y),(y,x)}).

  • Assume that X=X j for j∈I. Then βˆ€i∈I-{j}, βˆ€x i ∈X i , (x i ,y)∈E(G '' ) whenever i is less than j with respect to Οƒ and (y,x i )∈E(G '' ) whenever j is less than i with respect to Οƒ.

Clearly |E(G '' )|-|E(G ' )|β‰₯2|X|+1+|V(G ' )|-|X|-(2Β·|Y|-1+|V(G ' )|-|Y|)=|X|-|Y|+2 and since X is of maximal cardinality the difference is strictly positive. As E(G)βŠ†E(G ' ), |E(G '' )|-|E(G)| is also strictly positive. Now as 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G '' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G), 𝐍𝐒𝐂𝐂(G '' )=𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G) and as T(G '' )=T(G ' )-1=T(G)-1 the result holds by induction hypothesis.

Proposition 101

𝐍𝐀𝐑𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐒𝐂𝐂-1 2

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐒𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯(𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐍𝐒𝐂𝐂)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐒𝐂𝐂+1 2 +(𝐍𝐒𝐂𝐂-𝐍𝐕𝐄𝐑𝐓𝐄𝐗 mod 𝐍𝐒𝐂𝐂)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐒𝐂𝐂 2

Figure 4.3.4. Illustration of PropositionΒ 147. A graph that achieves the minimum number of arcs according to a fixed number of strongly connected components as well as to a fixed number of vertices (π™½πš‚π™²π™²=7,π™½πš…π™΄πšπšƒπ™΄πš‡=10,π™½π™°πšπ™²=10-7 2=7)
ctrs/preface-221-tikz

Proof 101 For proving partΒ 147 of PropositionΒ 101 we proceed by induction on 𝐍𝐒𝐂𝐂(G). If 𝐍𝐒𝐂𝐂(G)=1 then, we have 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G) (i.e., for one vertex this is true since every vertex has at least one arc, otherwise every vertex v has an arc arriving on v as well as an arc starting from v, thus we have 𝐍𝐀𝐑𝐂β‰₯2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2). If 𝐍𝐒𝐂𝐂(G)>1 let X be a strongly connected component of G. Then 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐀𝐑𝐂(G[V(G)-X])+𝐍𝐀𝐑𝐂(G[X]). By induction hypothesis 𝐍𝐀𝐑𝐂(G[V(G)-X])β‰₯|V(G)-X|-𝐍𝐒𝐂𝐂(G[V(G)-X])-1 2, thus 𝐍𝐀𝐑𝐂(G[V(G)-X])β‰₯|V(G)-X|-(𝐍𝐒𝐂𝐂(G)-1)-1 2. Since 𝐍𝐀𝐑𝐂(G[X])β‰₯|X| we obtain 𝐍𝐀𝐑𝐂(G)β‰₯|V(G)|-(𝐍𝐒𝐂𝐂(G)-1)-1 2, and thus the result holds.

Proposition 102

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐕𝐄𝐑𝐓𝐄𝐗>0⇒𝐍𝐒𝐂𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 𝐍𝐀𝐑𝐂

Proof 102 As shown inΒ [BessiereHebrardHnichKiziltanWalsh05], a lower bound for the minimum number of equivalence classes (e.g.,Β strongly connected components) is the independence number of the graph and the right-hand side of PropositionΒ 102 corresponds to a lower bound of the independence number proposed by TurΓ‘nΒ [Turan41].

Proposition 103

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐍𝐕𝐄𝐑𝐓𝐄𝐗>0⇒𝐍𝐒𝐂𝐂β‰₯2·𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐀𝐑𝐂-𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐀𝐑𝐂-𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐀𝐑𝐂-𝐍𝐕𝐄𝐑𝐓𝐄𝐗 𝐍𝐕𝐄𝐑𝐓𝐄𝐗+1

Proof 103 SeeΒ [Hansen75] andΒ [FavaronMaheoSacle88].

Proposition 104

𝐍𝐀𝐑𝐂≀(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-ππ’πˆππŠ)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 104 The maximum number of arcs is achieved by the following pattern: for all non-sink vertices we have an arc to all vertices.

Proposition 105

𝐍𝐀𝐑𝐂β‰₯ππ’πˆππŠ+max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2Β·ππ’πˆππŠ)

Figure 4.3.5. Illustration of PropositionΒ 105. Two graphs that achieve the minimum number of arcs according to a fixed number of sinks as well as to a fixed number of vertices: (A)Β π™½πš‚π™Έπ™½π™Ί=3,π™½πš…π™΄πšπšƒπ™΄πš‡=5,π™½π™°πšπ™²=3+max(0,5-2Β·3)=3; (B)Β π™½πš‚π™Έπ™½π™Ί=3,π™½πš…π™΄πšπšƒπ™΄πš‡=9,π™½π™°πšπ™²=3+max(0,9-2Β·3)=6.
ctrs/preface-222-tikz

Proof 105 Recall that for x∈V(G), we have that d G + (x)+d G - (x)β‰₯1. If x is a sink then d G - (x)β‰₯1, consequently 𝐍𝐀𝐑𝐂(G)β‰₯ππ’πˆππŠ(G). If x is not a sink then d G + (x)β‰₯1, consequently 𝐍𝐀𝐑𝐂(G)β‰₯|V(G)|-ππ’πˆππŠ(G).

Proposition 106

𝐍𝐀𝐑𝐂≀(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-ππ’πŽπ”π‘π‚π„)·𝐍𝐕𝐄𝐑𝐓𝐄𝐗

Proof 106 The maximum number of arcs is achieved by the following pattern: for all non-source vertices we have an arc from all vertices.

Proposition 107

𝐍𝐀𝐑𝐂β‰₯ππ’πŽπ”π‘π‚π„+max(0,𝐍𝐕𝐄𝐑𝐓𝐄𝐗-2Β·ππ’πŽπ”π‘π‚π„)

Figure 4.3.6. Illustration of PropositionΒ 107. Two graphs that achieve the minimum number of arcs according to a fixed number of sources as well as to a fixed number of vertices: (A)Β π™½πš‚π™Ύπš„πšπ™²π™΄=3,π™½πš…π™΄πšπšƒπ™΄πš‡=5,π™½π™°πšπ™²=3+max(0,5-2Β·3)=3; (B)Β π™½πš‚π™Ύπš„πšπ™²π™΄=3,π™½πš…π™΄πšπšƒπ™΄πš‡=9,π™½π™°πšπ™²=3+max(0,9-2Β·3)=6.
ctrs/preface-223-tikz

Proof 107 Similar to PropositionΒ 105.

Proposition 108

𝐍𝐒𝐂𝐂β‰₯ππ’πˆππŠ+ππ’πŽπ”π‘π‚π„

Proof 108 Since sinks and sources cannot belong to a circuit and since they cannot coincide (i.e., because isolated vertices are not allowed) the result follows.

Proposition 109

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯ππ’πˆππŠ+ππ’πŽπ”π‘π‚π„

Proof 109 No vertex can be both a source and a sink (isolated vertices are removed).