Graph theory: Existence of cycles

[sedeki]

Homework Statement

Let G be a graph containing a cycle C, assume that G contains a path P of length at least k between two verticies on C.
Show that G contains a cycle of length at least √k.

The Attempt at a Solution

Since C is a cycle, there are two paths between a and b. If P intersects none or one of these paths there is no problem.
If P intersects both there is a problem.

In the case of one intersection of both paths, there is cycle of length at least k/2 by combining pieces of C and pieces of P. Draw this to see what I mean.

(No solution for intermediate steps)

If P intersects P in more than √k places, then C is of length at least √k.

 

[lippyka]

Let's prove this by contradiction. Assume C is of length less than √k. Then P must intersect one of the paths at least (k-√k)+1 times.But then, since each intersection adds at least 2 to the length of the cycle, we have a contradiction. Therefore, G must contain a cycle of length at least √k.