1. The problem statement, all variables and given/known data 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. 3. 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.