Cycles in a directed graph

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 cyc开发者_如何学运维le of length 3 i.t either t->v1->v2->t or t->v2->v3->t. But an not being able to proof this.

Thanks

---

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!

---

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.

---

Simple proof:

1. Assume t is part of a cycle which includes va and vb, and other nodes, where there is an edge t -> va and vb -> t

2. then there is a sequence of nodes [vc, vd, ve...] in the cycle between va and vb;

3. Take the first node in the set - vc. There is either an edge from t to vc, or from vc to t (as you have stated);

4a. if the edge is from t to vc, then there is a shorter cycle than the one involving [t, va, vb], because we can skip from t directly to vc, bypassing va; furthermore, if this new cycle is of length greater than 3, this process can then be repeated on the new cycle starting from step 1.

4b. Otherwise, the edge is from vc to t, and there is a cycle of length 3 - t to va, va to vc, vc to t.

Therefore, any cycle can be reduced to length 3.