I have a question from class that is as follows:
Consider random walk on a graph G = (V, E). Suppose that you are at a node u ∈ V. Given a node w different from u, what is the expectation for the number of steps to reach w starting from u? The questions can have dramatically different answers depending on whether G is directed or undirected. Assume G is a line graph.
Show that if G is an undirected line graph, then the expected steps of visiting w from u is $cn^2$ where $c$ is a constant.
I have a feeling that this question might just be posed poorly by my professor, but I did get them to tell me that $n$ is supposedly the total number of nodes in the graph. I'm not sure exactly what is meant by a "undirected line graph", i.e. does that mean a graph where every node has exactly 2 edges?
In my mind, it would seem that the distance between nodes $u$ and $w$ would have to play some role in the answer, and I'm not sure why the total nodes matters at all.
My question is does anyone have any advice of how to interpret or approach this problem such that the expected number of steps is proportional to $n^2$?