[Solved]: How many edges can a unipathic graph have?

Problem Detail: 

A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.

Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of length 2, for a total of $2(n-1)$.

What is the maximum number of edges in a unipathic graph with $n$ vertices? An asymptotic bound would do (e.g. $O(n)$ or $\Theta(n^2)$).

_{Inspired by Find shortest paths in a weighed unipathic graph; in my proof, I initially wanted to claim that the number of edges was $O(n)$ but then realized that bounding the number of cycles was sufficient.}

Asked By : Gilles

Answered By : Gilles

A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges.

Consider a complete bipartite graph, with oriented edges $\forall (i,j) \in [1,m]^2, a_i \rightarrow b_j$. This graph is unipathic and has no cycle: all its paths have length $1$. It has $2m$ vertices and $m^2$ edges.

_{(Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/680