# What is the minimum number of edges a graph can have with strongly connected components of at least $3$ vertices each?

This is a homework question that has me stumped:

Let $$G$$ be a directed graph with $$\boldsymbol n$$ vertices and $$\boldsymbol k$$ strongly connected components (with $$1 < k \leq \left\lfloor\dfrac{n}{3}\right\rfloor$$). We also know that each strongly connected component has at least $$3$$ vertices. What is the minimum number of edges that $$G$$ may have?

I know that if $$G$$ is a directed graph with $$n$$ vertices and $$k$$ strongly connected components (with $$k > 1$$), the minimum number of edges that $$G$$ may have can be calculated with: $$\boldsymbol{n - k + 1}$$.

My initial hunch is that the general formula needs to be modified to account for the strongly connected component with at least $$3$$ vertices, but I'm not sure which approach to take and, most importantly, what properties to use.

• Have you tried to find examples with at least 3 vertices in each of three strongly connected components? Of course such "components" might share vertices and directed edges. – hardmath Nov 26 '18 at 0:17
• My initial thought is a graph like this: Imgur So the end result would be n = 6, k = 2 leading to 6 - 2 + 1 = 4 edges. But that doesn't fit the homework question. – shatter Nov 26 '18 at 0:32
• I see only two strongly connected components (vertices must be mutually reachable by directed paths in such a component). Of course we can give the easy example of three independent 3-cycles, so 9 edges is an upper bound. – hardmath Nov 26 '18 at 0:37
• Do you know a proof of the $n-k+1$ formula? That ought to shed some insight on what needs to be modified to account for the additional requirement that each SCC contains at least $3$ vertices. – Henning Makholm Nov 26 '18 at 2:19
• @hardmath As I understand it, a strongly connected component cannot share any vertices with another strongly connected component. Complicating matters is each component must have at least 3 vertices. Using the 9 edge example you provided, all components would share one vertex each. I thought of something similar, but it would use 11 edges, with 3 * 3 edges + 2 edges bridging the three strongly connected components. – shatter Nov 26 '18 at 3:33