I have a task "We have a graph G, which is directed and has 10 vertices. It has no parallel edges and has no loops. Also we know that G has 3 components and 5 strongly-connected components.
What is the minimum amount of edges that G can have?
What is the maximum amount of edges that G can have?"
How do I calculate this?
Since $G$ has $5$ strongly-connected components, it has a strongly-connected component $H$ consisting of at least $2$ vertices. We can remove an edge $e$ from $H$, keeping its connected. Then $G$ without $e$ still has $3$ connected components. A connected component consisting of $k$ vertices has at least $k-1$ edges, so $G$ has at least $7+1=8$ edges. This value is attained, for instance, when $G$ is a disjoint union of a directed cycle on six vertices and two copies of a graph on two vertices with a single directed edge.
If connected components of $G$ have $n_1$, $n_2$, and $n_3$ vertices then $G$ has at most ${10\choose 2}-(n_1n_2+n_1n_3+n_2n_3)$ edges.
Let us estimate $n_1n_2+n_1n_3+n_2n_3$ from below. Suppose that there exists distinct $i,j$ such that $1<n_i\le n_j$. Say, $1<n_1\le n_2$. Put $n_1’=n_1-1$ and $n_2’=n_2+1$. Then $$n_1n_2+n_1n_3+n_2n_3- n_1’n_2’+n_1’n_3+n_2’n_3=$$ $$n_1n_2+n_1n_3+n_2n_3- (n_1-1)(n_2+1)+(n_1-1)n_3+(n_2+1)n_3=$$ $$n_1n_2- (n_1-1)(n_2+1)=n_2-n_1+1>0.$$
Thus the minimum of $n_1n_2+n_1n_3+n_2n_3$ is attained when two of $n_i$’s equal $1$, so $G$ has at most ${10\choose 2}-(1\cdot 1+1\cdot 8+1\cdot 8)=28$ edges. This value is attained, for instance, when $G$ is a disjoint union of two isolated vertices and a tournament on eight vertices, which contains a directed cycle on six vertices and two remaining vertices have only ingoing edges.