0
$\begingroup$

An exercise in Introduction to Graph Theory by Robin J. Wilson asks for a proof that, if $D$ is a simple directed graph with $n$ vertices and $m$ arcs which is connected but not strongly connected, then

$$n - 1 \le m \le (n-1)(n-2).$$

I believe this to be incorrect, but I do think I have a proof that $$n-1 \le m \le (n-1)^2.$$

Let $v_1, v_2, \dots, v_n$ be the vertices of $D$.

Since $D$ is weakly connected, it follows that $D$ has at least $n-1$ edges, as if $D$ had $n-2$ or fewer edges, then it's underlying graph (the graph formed by treating arcs as undirected edges) would be disconnected. Moreover, the graph with arc set $S = {(v_1, v_2), (v_2, v_3), \dots, (v_{n-1}, v_n)}$ is not strongly connected (as no path exists between $v_n$ and any other vertex), so this inequality is not strict.

To establish the upper bound, define $D$ such that, for $i < n, i \ne j, (v_i, v_j)$ is an arc in $D$. Such a grpah has $(n-1)^2$ edges and is connected, but not strongly connected, as $v_n$ has no outbound arcs and thus no exists from $v_n$ to any other vertex. To show that this is indeed the upper bound, consider a simple connected digraph $H$ on $n$ vertices with at least $(n-1)^2 + 1$ arcs. Since $D$ is simple, each vertex of $D$ can have at most $n-1$ incoming arcs and $n-1$ outgoing arcs. Since each arc is directed toward one vertex and away from another, it follows by the pigeonhole principle that each vertex of $H$ has at least on incoming arc and one outgoing arc. We will show that such a graph must be strongly connected by induction.

Let $H_n$ be the set of all graphs on $n$ vertices with at least $(n-1)^2 + 1$ arcs. For the base case, any graph in $H_1$ and $H_2$ is obviously strongly connected. Suppose any graph in $H_n$ is strongly connected for some $n$, and consider a graph $D$ in $H_{n+1}$. Let $k$ be the minimum number of outgoing edges for any vertex. If $k = n$, then any two vertices are connected by arcs in opposite directions, so $D$ is strongly connected and we are done. Alternatively, suppose that $0 < k < n-1$. Then, if $D$ is not strongly connected, if follows that there exist vertices $v$ and $w$ such that no path exists from $v$ to $w$. Let $u$ be a vertex such that an edge exists from $v$ to $u$, and consider the directed graph $D'$ with $v$ and all arcs incident to it removed. $D'$ will have at least $(n+1-1)^2 +1 - k - (n-1) > n^2 - 2n +1 +1 = (n-1)^2 + 1$ arcs, and will thus be in $H_n$. Now, $u$ and $w$ will be in $D'$, and as $D' \in H_n$, it follows that a path exists from $u$ to $w$. But, this means there exists a path from $v$ to $u$ to $w$ in $D$, contradicting the original assumption. Thus, $D$ is strongly connected.

Does this proof look correct? Moreover, could it be improved? I don't have much experience in graph theory, so I'm not sure if there's some standard form for graph-theoretical proofs I should be using.

$\endgroup$
1
$\begingroup$

Assume by way of induction that all simple directed graphs with $n$ nodes have no more than $(n-1)(n-2)$ edges. Any graph with $n+1$ nodes can be composed from a graph with $n$ nodes by adding a node and some edges.

[UPDATE -- see comments] Let a maximal simple directed graph be one to which no edges can be added without violating simplicity. Any maximal $n+1$-node simple graph can be composed from a $n$-node maximal simple graph by adding edges only between the new node and pre-existing nodes. (The two claims: that any maximal $n+1$ graph can be composed, and that no other edges can be added, are both easy to verify.)

In fact, after adding new node $n+1$, we can add no more than $n$ edges (one for each previously existing node), as to add more would create a trivial cycle. Thus, if previously we had $(n-1)(n-2)$ edges, now we will have:

\begin{align} (n-1)(n-2)+n &= n^2-2n-2 \\ &= n(n-1) -n + 2 \\ &\leq n(n-1) \quad\text{ for $n >= 2$} \end{align}

As the $n=1$ case is trivial, this proves the tighter bound Wilson asks for.

$\endgroup$
  • $\begingroup$ Sorry it took me a while to get back to you. Could you explain why we can add no more than $n$ edges? It seems to me that, if you made all of the $n$ edges go into the new vertex, then you could also add edges between pre-existing nodes without making the graph strongly connected. $\endgroup$ – Strants Mar 24 '14 at 18:05
  • $\begingroup$ If we start with an $n$-node graph to which we can add edges, we could have equally well started with that graph except with those edges already added in. The new starting graph would still have no more than $(n-1)(n-2)$ edges by the induction hypothesis. $\endgroup$ – shaunc Mar 26 '14 at 20:49
  • $\begingroup$ So what about, for example, the graph $D = (V, E)$, with $V = {0, 1, 2}$ and $E = {(0,1), (1,0), (0,2), (1,2)}$? For this graph, $n=3, m=4$, so $m > (n-1)(n-2) = 2$. $\endgroup$ – Strants Mar 26 '14 at 22:22
  • $\begingroup$ Hmm... if simple means "no more than one edge between any two nodes" than that isn't a valid simple graph, as there are two edges between 0 and 1. If it means "no more than one edge of a given direction between any two nodes", then, given $n$ nodes, you can insert $2n$ edges to a newly introduced node. With 3 nodes you could have 6 edges -- back and forth between each pair, which would invalidate your proof too. $\endgroup$ – shaunc Mar 27 '14 at 2:28
  • $\begingroup$ It's a little hard to tell, seeing as Wilson only says "a simple digraph is defined in the obvious way." en.wikipedia.org/wiki/Directed_graph and mathworld.wolfram.com/SimpleDirectedGraph.html don't seem to agree, so I guess it's safe to assume that Wilson defines a simple digraph in the sense that you do. Thanks for the help! $\endgroup$ – Strants Mar 27 '14 at 3:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.