3
$\begingroup$

I am looking for a proof of a particular theorem. The theorem would state:

Every finite, weakly connected digraph contains at least one source or cycle.

Since every finite graph is either cyclic or acyclic, an alternative statement would be:

Every finite, weakly connected, acyclic digraph has a source.

with the previous theorem as a corollary.

Note: Assuming that the above is correct, then for any natural number $n$, an effective procedure exists to show that every weakly connected, acyclic digraph with fewer than $n$ vertices has a source - namely, "pick a point and backtrack". While this makes the theorem seem trivial, it is insufficient to prove that every finite, weakly connected, acyclic digraph has a source, hence the request for a proof.


I checked the library, all of my textbooks, and searched online, but I can't seem to find any reference to this theorem. The notion seems sufficiently obvious so as to be a fundamental result in graph theory, but no one I've spoken to has been able to put a name to it.

Is there a name for this theorem (or other, more significant theorem from which it can be easily derived), and where can I find a proof of it?

$\endgroup$
0
$\begingroup$

I don't know of a particular name for the theorem, but the idea of "pick a point and backtrack" is pretty much a proof - you can formalize it as follows, by proving the contrapositive:

Let $G$ be a finite non-empty directed graph, none of which is a source. Then $G$ is cyclic.

Then to prove it, let $n$ be the number of vertices and let $x_0$ be an arbitrary vertex. Choose a sequence $x_1,\ldots,x_n$ with the property that $x_i$ has an edge to $x_{i-1}$. This is possible since there are no sources. However, now we have a sequence $x_0,\ldots,x_n$ with $n+1$ elements, thus by the pigeonhole principle, some pair must be the same - that is $x_i=x_j$ for some $j\neq i$. Assume without loss of generality that $i>j$. Then $$x_i\rightarrow x_{i-1} \rightarrow \ldots \rightarrow x_{j+1} \rightarrow x_j$$ is a cycle*.

(*If you insist upon a simple cycle, you can choose the a $(i,j)$ with $x_i=x_j$ and $i\neq j$ that minimizes $|i-j|$, since we know that the set of such pairs is non-empty)

$\endgroup$
0
$\begingroup$

The digraph doesn't even need to be weakly connected, just non-empty.

Let $W$ be a directed walk in the digraph $D$ of maximal length. (As $D$ is acyclic, the length of directed walks is bounded above by the number of nodes in $D$, so this is a valid construction.) Consider $v$, the origin of $W$. Since $D$ is acyclic, $D$ does not have an arc with $v$ as its tail whose head is another vertex in $W$. Since $W$ is of maximal length, $D$ does not have an arc with $v$ as its tail whose head is vertex not in $W$. Therefore, $v$ is a source.

$\endgroup$
  • $\begingroup$ Well, but nonemptiness does not suffice though. Also, a digraph can be not strongly connected but still be such that every vertex has indegree and outdegree at least one. Indeed take two vertex-disjoint directed cycles and put a directed edge from a vertex in one cycle to a vertex in another. The property of being acyclic--connected or not--does suffice though. $\endgroup$ – Mike Oct 9 at 18:10
  • $\begingroup$ @Mike Yeah, but still the origin of every maximal-length directed path in an acyclic directed graph (not even maximum, just something that is not a "subgraph" or a longer directed path) is a source. Actually, now that I look at a definition, an isolated vertex is both a source and a sink, so really the digraph just needs a single vertex and no directed cycles to have a source. $\endgroup$ – Matthew Daly Oct 9 at 20:34
  • $\begingroup$ Yes indeed. What you said in the 2nd paragraph of your answer is fine. The starting point of every maximal path [doesn't have to be maximum] is indeed a source. I do think the first paragraph of your answer may mislead some to say that every nonempty finite digraph has a source and of course that is not the case. $\endgroup$ – Mike Oct 9 at 23:03

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.