edited by
403 views
1 votes
1 votes
Suppose that G contains a cycle C, and a path of length at least k between some two
vertices of C. Show that G contains a cycle of length at least √k.
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
dan31 asked Feb 17, 2019
469 views
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decr...
1 votes
1 votes
0 answers
2
dan31 asked Feb 17, 2019
389 views
Give an efficient algorithm for maximum size rectangle binary sub-matrix with all 1s . [Complexity should be O($n^c$)](Memory based – Original question had a lot of ad...
0 votes
0 votes
0 answers
4
dan31 asked Feb 17, 2019
575 views
Determine the number of functions f:{1,2,3…,n}→{1995,1996} satisfying the condition that f(1)+f(2)+…f(n) is odd.