- #1
sedeki
- 1
- 0
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.