What is the maximum number of arcs $D$ can have if $D$ is a digraph with $n$ vertices that is unilaterally connected but not strongly connected?
This is a question from my graph theory course homework. I believe from some research that the answer is $2\binom{n-1}{2} +(n-1)=(n-1)(n-2)+(n-1)=(n-1)^2$. However, I am not sure how to show this or if it is even correct. Some guidance on how to go about this problem would be greatly appreciated. If anything needs to be clarified please let me know!
Best Answer
I believe your answer is correct. Such a graph can be achieved by taking all of the $2\binom{n}{2} = n(n-1)$ possible edges and removing all $n-1$ edges coming out of a fixed vertex, leaving us with $(n-1)^2$ edges. This graph is easily seen to be unilaterally connected, but is not strongly connected since it has a sink.
Now let $G$ be a directed graph that is not strongly connected. Let $X$ be a connected component, assume it has $c$ vertices. Let $O(X)$ and $I(X)$ be the vertices not in $X$ such that:
$v\in O(X)$ if there is an edge from $X$ to a vertex of $v$.
$v\in I(X)$ if there is an edge from $v$ to $X$.
Note there are at least $c( (n-c) -|O(X)|) + c( (n-c) - |I(X)|) = c(2(n-c) - |O(X)| - |I(X)|)$ edges that are not in $G$.
Note that $O(X)$ and $I(X)$ cannot intersect because a vertex in the intersection must be in the same strongly connected component as the vertices in $X$.
It follows there are at least $c(n-c)$ edges that are not in $G$. And this number is at least $n-1$.
Therefore there is no non-strongly connected graph with more edges than the example we give at the beginning.