The problem I am working on is as follows:

Let $G$ be a graph with $n$ vertices and at most $r>=2$ independent vertices (no two are adjacent). Prove that if D is an orientation of G which does not contain a directed cycle then $D$ contains a directed path of length at least ⌈$n/r$⌉$-1$.

I have a theorem proven in class that says every directed graph has a path cover with the number of paths at most the size of the maximum independent set of vertices, and since there are always r paths that cover n vertices, if the paths have large differences in size one of them should easily be bigger than ⌈$n/r$⌉$-1$, and if they're as equal as possible then the largest of them (or if they're all equal, any one of them) will have size $n/r$ or $(n+k)/r$ for some positive integer $k$, and $(n+k)/r > n/r >= $⌈$n/r$⌉$-1$. But if this works (and I'm doubtful it does for exactly this reason), then why does D need to contain no directed cycles?


1 Answer 1


I agree with you that the problem is oddly stated. The assumption that $D$ is acyclic is superfluous, as is the condition $r\ge2$, and there is no need to mention the undirected graph $G$. I would have stated it this way: "If $D$ is a directed graph with $n$ vertices and at most $r$ independent vertices, then $D$ contains a directed path of length $\lceil n/r\rceil-1$."

I find your discussion a little confusing. What do you mean by the "size" of a path? the number of vertices or the number of edges? I would explain it this way:

By the (Gallai-Milgram) theorem about path covers, the vertices of $D$ can be covered by a set of $r$ paths. The longest of those paths has $m$ vertices where $m\ge n/r$. Since $m$ is an integer, this means that $m\ge\lceil n/r\rceil$. Since the path has $m$ vertices, its length is $m-1\ge\lceil n/r\rceil-1$.

  • $\begingroup$ My explanation was kind of informal, but I meant the length of the path, which is the number of edges. $\endgroup$
    – Xindaris
    Oct 6, 2013 at 13:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .