# length of a walk in product graph

I was doing tensor product of graphs. We know that to find a walk between every two vertices x and y of any arbitrary length l in G, the graph must contain an odd cycle. I am stuck here. Is it possible to find l that is common for every pair of vertices. I mean to find an l such that every pair of vertices have a walk of length l between them. Or any particular type of graph where this is possible. Any kind of help or suggestion will be helpful, Thanks a lot.

Can we find such n that satisfies the Prop 5.7 for every pair of vertices in G and H? Actually i want the max{d(a,b),(c,d)} where a and c are in G, b and d are in H

Also Its related to my last post on thi page. I hope the following link will help

Is it possible to have a walk between every two vertices of any arbitrary length in a graph?

-
What do you mean by:"We know that to find a walk between every two vertices x and y of any arbitrary length $l$ in $G$, the graph must contain an odd cycle". If $l=1$ it's not sufficient, is it? –  wece Jul 29 '13 at 18:29

In the previous question you link to in this question, the answer by Doug Stones shows, assuming the graph is not bipartite, why for each pair $(x,y)$ of vertices there is a positive integer $L$ such that, for each length $l\ge L$, there is a path from $x$ to $y$ of that length $l$.
Since a graph with $n$ vertices has less than $n^2$ pairs $(x,y)$ of vertices for which a path is sought, you can use the above result and define $L^*$ to be the maximum value of $L(x,y)$ for all the pairs $(x,y)$ of vertices, where by $L(x,y)$ is meant some choice of $L$ for vertices $x,y$ as in the result above. Then if you choose any particular $l \ge L^*$ there will be (uniformly in the choice of $x,y$) a path of that length $l$ from $x$ to $y$.
@monalisa That is correct, if $L'$ is the max of all the $L$, one $L$ for each pair $(x,y)$ of vertices in the graph. I just called that max by the symbol $L^*$ instead of $L'$. Also the same thing holds if we look at any fixed length $L''\ge L'.$ –  coffeemath Jul 30 '13 at 2:28