Cycles in a directed graph

Question

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

Let v1,v2,v3...vn and t be n+1 vertexes in a directed graph. v1,v2,v3...vn form directed acyclic graph. t is connected to each and everyone of v1,v2,v3...vn. Now since v1,v2,v3...v4 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 v1,v2...vn and there is no pair wise cycle.

Explaining the problem further.

Say the acyclic directed graph of vertices v1,v2,v3..vn is v1->v2->v3->...vn. Each v has an edge to t. Say there is a cycle t->v1->v2->v3->t. Such a cycle seems to surely involve a cycle of length 3 i.t either t->v1->v2->t or t->v2->v3->t. But an not being able to proof this.

Thanks

Answer 1

LET US USE THE METHOD OF PROOF BY CASES:

(since it is difficult to type the notations, I scanned the handwritten pages and I attach here for your reference.)

Let us consider a Graph G,with vertices v1,v2,v3...vn. And let Graph G be an acyclic directed graph.

If k=0, it is obvious case that t->vi->vj->t has a sub-cycle of length 3.

Hence Proved.

Hope that helps!

Answer 2

The basic idea is that the shortest cycle has length 3 because (I assume that) t is connected to any other vertex through one and only one edge, and the other vertices do not form cycles without t.

So a cycle has at least t and two other vertices.

Any path between two vertices that form a cycle with t has length 3 or more.

For such a cycle, you can find two vertices on the path directly connected to each other (neighbors) that are both connected to t, therefore they form a cycle with length 3.

Imagine the path between v[a] and v[b] as a section of a wheel, and the connections of the vertices v[i] on the path to t as spokes... you can always find a shorter section between v[a] and v[b].

[ADDITION FOR DIRECTED GRAPH]
Let v[a] come from t and v[b] go to t and v[a] leading up to v[b]. If the cycle between v[a] and v[b] is length 3, the statement holds. Otherwise there must either be one vertex after v[a] going to t (but not v[b]), or a vertex before v[b] coming from t (but not v[a]) whose cycle is at least one shorter (there are only two directions to choose from: from t or to t). Repeat with the shorter cycle until you reach length 3.