Typically a walk is defined as a vertex-edge sequence, e.g. $(v_1, e_1, v_2, e_2, v_3)$, but suppose we are working in the undirected simple graph setting. Instead, let's say an edge-sequence $(e_1, e_2)$ is a walk from vertex $v_1$ to $v_3$ if we can recover the full vertex-edge sequence definition by inserting vertices into the edge-sequence reasonably, i.e. if a vertex precedes or follows an edge in the sequence it must be incident to that edge. This edge-sequence notation makes things ambiguous in the sense that $(e)$ can represent two walks going in either direction along the edge, but we won't worry about this.

My most general question: For a given graph $G$, is there an efficient way to count the number of edge-sequences of length $k$ that contain at least one subsequence which is a walk from vertex $i$ to vertex $j$?

I imagine this might be difficult for generic graphs, so let's focus on the case where the graph is the complete graph, $K_n$. There are ${n\choose 2}^k$ edge sequences of length $k$. How many of these contain at least one subsequence which is a walk between two distinct vertices $i$ and $j$?

First two cases: If $k=1$, then there is only one sequence: the one consisting of the edge between the vertices, call it $(e)$. If $k=2$, the way I tried to do this is by systematically building all the sequences from smaller walks and filling the rest of the sequence with dummy edges. There are $n-2$ walks of length $2$ and no need for dummy edges. There's only walk of length 1, so we can have sequences $(e,\bar{e})$ and $(\bar{e},e)$ where $\bar{e}$ represents any of the ${n\choose 2}$ edges. We must be careful about double counting though, there aren't $2{n\choose 2}$ choices for inserting the dummy edge, but rather, $2{n\choose 2}-1$. Thus, we have there are $(n-2)+ 2{n\choose 2}-1$ sequences of length two that contain at least one subsequence which is a walk between two distinct vertices. The case for $k=3$ is way hairier: when building up sequences from walks of length 1 we get ${n\choose 2}^2+{n\choose 2}\left({n\choose 2}-1\right)+\left({n\choose 2}-1\right)^2$ but some of these are the same as the $(n-2)(3{n\choose 2} -2)$ we get when building up from walks of length 2.

I'd appreciate any references or if anyone has seen this quantity or something similar I'd love to know about it. Perhaps there's something else it can be mapped to that's easier to digest.

For context, this quantity came up while I was studying contact processes on networks. Thanks!