Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a conjecture about odd cycle in a simple graph,but I can not proof it or find a counterexample.So I want to ask for some help.My conjecture is:

Let k be a positive integer and G be a 2-connected simple gragh satisfy:

(1)G is not complete;

(2)For every two different vertices u and v of G which are not adjacent, there exists a path link u and v whose length is odd and not less then 2k+1.

Then there must exists an odd cycle in G whose length is not less than 2k+1.

share|improve this question

migrated from mathoverflow.net Sep 17 '13 at 11:23

This question came from our site for professional mathematicians.

Sorry,it is my first time to ask a question on math.stackexchange and mathoverflow. –  user40096 Sep 17 '13 at 6:00
I assume that "path" means "simple path", right? –  Brendan McKay Sep 17 '13 at 6:21
isn't a proof for $k=1$ trivial? Take 2 vertices $u_0,u_2$ at distance 2 (say, $u_0u_1u_2$ is a path connecting them). Then there should be a length $2k+1=3$ path $u_0v_1v_2u_2$ between them, too. Now take all the vertices $u_i$ and $v_j$ - they form a 5-path, right? –  Dima Pasechnik Sep 17 '13 at 6:29
hello,Brendan McKay,I do not know what does the "simple path"mean. –  user40096 Sep 17 '13 at 10:38
hello,Dima Pasechnik,you are right.When k=1,the proof is very simple.But in your proof,v1 or v2 maybe u1.Of course,when this happens,we can also get a 3-cycle. –  user40096 Sep 17 '13 at 10:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.