1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Why are you interested in this problem? $\endgroup$ – Aaron Sterling Sep 1 '11 at 4:12
  • 4
    $\begingroup$ In my mind, this almost sounds like a homework problem. $\endgroup$ – Timothy Sun Sep 1 '11 at 5:20
  • 1
    $\begingroup$ 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"... $\endgroup$ – Ryan Williams Sep 1 '11 at 5:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Sep 1 '11 at 9:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Sep 1 '11 at 9:04

Your Answer

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

Browse other questions tagged or ask your own question.