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.

  • $\begingroup$ 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. $\endgroup$ – hardmath Nov 26 '18 at 0:17
  • $\begingroup$ 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. $\endgroup$ – shatter Nov 26 '18 at 0:32
  • $\begingroup$ 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. $\endgroup$ – hardmath Nov 26 '18 at 0:37
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 26 '18 at 2:19
  • $\begingroup$ @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. $\endgroup$ – shatter Nov 26 '18 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.