<p>Wondering if we can prove the following or if it is already proved where can I get the proof.</p>

<p>Let $v_1, v_2, v_3, \ldots, v_n$ and $t$ be $n+1$ vertexes in a directed graph. $v_1, v_2, v_3, \ldots, v_n$ form directed acyclic graph. $t$ is connected to each and everyone of $v_1, v_2, v_3, \ldots, v_n$. Now since $v_1, v_2, v_3, \ldots, v_n$ are connected in an acyclic manner, if there is a cycle then it will involve $t$. Can we show that all cycles of length more then 3 will always involve a cycle of length 3? Remember $t$ is connected to every $v_1, v_2, v_3, \ldots, v_n$ and there is no pair wise cycle.</p>

<p>Are there any other similar problems with different wordings?
Thanks</p>

<p>I have probably not worded the question more clearly.</p>

<p>Say the acyclic directed graph of vertices $v_1, v_2, v_3, \ldots, v_n$ is $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow \cdots \rightarrow v_n$. Each $v$ has an edge to $t$. Say there is a cycle $t \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow t$. Such a cycle seems to surely involve a cycle of length 3 i.t either $t \rightarrow v_1 \rightarrow v_2 \rightarrow t$ or $t \rightarrow v_2 \rightarrow v_3 \rightarrow t$. But an not being able to proof this. </p>

CC BY-SA 3.0
2011-09-03T01:07:54.960Z
Whether or not it is actually a homework problem, it could certainly be assigned as one without being considered cruel. While it was a fun puzzle, this just doesn't seem research-level for any branch of Computer Science, let alone TCS, regardless of justification.
Josephine Moeller
CC BY-SA 3.0
2011-09-01T04:12:16.947Z
Why are you interested in this problem?
Aaron Sterling
CC BY-SA 3.0
2011-09-01T04:49:07.017Z
@Aaron...Its part of a project i am involved in...explaining the details of which will involve a lot of space
Juggler
CC BY-SA 3.0
2011-09-01T05:18:34.303Z
Try examining the case where $v_1,\dotsc,v_n$ form a directed path.
Timothy Sun
CC BY-SA 3.0
2011-09-01T05:20:12.490Z
In my mind, this almost sounds like a homework problem.
Timothy Sun
CC BY-SA 3.0
2011-09-01T05:21:00.883Z
Some details are missing. Are the directions of arcs between t and $v_1$,$\ldots$,$v_n$ arbitrarily chosen, or do all the arcs go from $t$ to the others, or...? Also, what does it mean for a cycle of length more than 3 to "involve" a cycle of length 3? Do you mean there is a 3-cycle on some of the vertices in the larger cycle? Another possible interpretation: you are asking whether "there is a cycle" implies "there is a cycle of length 3"...
Ryan Williams
CC BY-SA 3.0
2011-09-01T05:32:25.340Z
@ryan and Timothy...I have added  bit more details. I am not a graph theoretic person and hence not good with the jargons. And its not a homework problem.
Juggler
CC BY-SA 3.0
2011-09-01T09:01:09.533Z
If there is a directed cycle of length $k+1$, then you have identified a directed path $(u_1, u_2, \dotsc, u_k)$ where $u_i \in \{v_1, v_2, \dotsc, v_n\}$, and the directed edges $(t,u_1)$ and $(u_k,t)$. Therefore if you check all edges $(t,u_1), (t,u_2), \dotsc, (t,u_k)$ in this order, you know that the first one is directed away from $t$ while the last one is directed towards $t$. Hence at some point you will necessarily find an index $i$ such that $(t,u_i)$ is the *last* edge directed away from $t$. Hence $(t,u_{i+1})$ is directed towards $t$, and you have found a triangle.
Jukka Suomela
CC BY-SA 3.0
2011-09-01T09:04:05.180Z
PS. The lack of graph-theory jargon was enough to convince me that this is not a homework problem from a graph-theory course. :)  Nevertheless, I think it would be good to tell us more about your motivation for solving the problem; in the current form it does not look like a research-level question.
Jukka Suomela
<ds.algorithms><graph-theory><directed-acyclic-graph>
Cycles in a directed graph
Juggler
# Cycles in a directed graph

(Asked by: username_0 on 2011-09-01)

Wondering if we can prove the following or if it is already proved where can I get the proof.

Let $v\_1, v\_2, v\_3, \ldots, v\_n$ and $t$ be $n+1$ vertexes in a directed graph. $v\_1, v\_2, v\_3, \ldots, v\_n$ form directed acyclic graph. $t$ is connected to each and everyone of $v\_1, v\_2, v\_3, \ldots, v\_n$. Now since $v\_1, v\_2, v\_3, \ldots, v\_n$ are connected in an acyclic manner, if there is a cycle then it will involve $t$. Can we show that all cycles of length more then 3 will always involve a cycle of length 3? Remember $t$ is connected to every $v\_1, v\_2, v\_3, \ldots, v\_n$ and there is no pair wise cycle.

Are there any other similar problems with different wordings?
Thanks

I have probably not worded the question more clearly.

Say the acyclic directed graph of vertices $v\_1, v\_2, v\_3, \ldots, v\_n$ is $v\_1 \rightarrow v\_2 \rightarrow v\_3 \rightarrow \cdots \rightarrow v\_n$. Each $v$ has an edge to $t$. Say there is a cycle $t \rightarrow v\_1 \rightarrow v\_2 \rightarrow v\_3 \rightarrow t$. Such a cycle seems to surely involve a cycle of length 3 i.t either $t \rightarrow v\_1 \rightarrow v\_2 \rightarrow t$ or $t \rightarrow v\_2 \rightarrow v\_3 \rightarrow t$. But an not being able to proof this.

**Tags:** ds.algorithms, graph-theory, directed-acyclic-graph
> **Comments:**
> **username_2**: Why are you interested in this problem?  
> **username_0**: @Aaron...Its part of a project i am involved in...explaining the details of which will involve a lot of space  
> **username_3**: Try examining the case where $v_1,\dotsc,v_n$ form a directed path.  
> **username_3**: In my mind, this almost sounds like a homework problem.  
> **username_4**: Some details are missing. Are the directions of arcs between t and $v_1$,$\ldots$,$v_n$ arbitrarily chosen, or do all the arcs go from $t$ to the others, or...? Also, what does it mean for a cycle of length more than 3 to "involve" a cycle of length 3? Do you mean there is a 3-cycle on some of the vertices in the larger cycle? Another possible interpretation: you are asking whether "there is a cycle" implies "there is a cycle of length 3"...  
> **username_0**: @ryan and Timothy...I have added  bit more details. I am not a graph theoretic person and hence not good with the jargons. And its not a homework problem.  
> **username_5**: If there is a directed cycle of length $k+1$, then you have identified a directed path $(u_1, u_2, \dotsc, u_k)$ where $u_i \in \{v_1, v_2, \dotsc, v_n\}$, and the directed edges $(t,u_1)$ and $(u_k,t)$. Therefore if you check all edges $(t,u_1), (t,u_2), \dotsc, (t,u_k)$ in this order, you know that the first one is directed away from $t$ while the last one is directed towards $t$. Hence at some point you will necessarily find an index $i$ such that $(t,u_i)$ is the *last* edge directed away from $t$. Hence $(t,u_{i+1})$ is directed towards $t$, and you have found a triangle.  
> **username_5**: PS. The lack of graph-theory jargon was enough to convince me that this is not a homework problem from a graph-theory course. :)  Nevertheless, I think it would be good to tell us more about your motivation for solving the problem; in the current form it does not look like a research-level question.  
> **username_1**: Whether or not it is actually a homework problem, it could certainly be assigned as one without being considered cruel. While it was a fun puzzle, this just doesn't seem research-level for any branch of Computer Science, let alone TCS, regardless of justification.  

---

## 0 answers

