Maximum hitting time for random walks on graphs with few edges For $x$ and $y$ vertices of a connected graph $G$, let $T_G(x,y)$ denote the expected time before a random walk starting from $x$ reaches $y$. What is the maximum possible value of $T_G(x,y)$ if the graph has to have at most $k$ edges?
I was initially interested in bounding the number of vertices instead of the number of edges. My first guess was that a line graph would be optimal giving $T_G(x,y)=(n-1)^2$ with $n$ vertices. But then I found Maximum Hitting Time for Random Walks on Graphs which shows that $T_G(x,y)$ can go up to $4n^3/27$ with $n$ vertices.
However the reason I got interested in the initial question was because I was studying grid mazes, and for $n$ large enough, the graph used to get $T_G(x,y)=4n^3/27$ is not possible to recreate with a grid maze, because it is not planar. Since planar graphs have a linear number of edges, I thought the most logical next step would be to try and restrict the number of edges instead of the number of vertices.
 A: There is a very useful identity for the hitting time in a random walk on a graph:
$$
   T_G(x,y) + T_G(y,x) = 2m \cdot R_G(x,y)
$$
where $R_G(x,y)$ is the effective resistance between $x$ and $y$. This effective resistance is at most the distance $d_G(x,y)$: that's what we'd get if there were a unique path between $x$ and $y$ in the graph, and adding more edges can only reduce the effective resistance. In particular, we get an upper bound of $T_G(x,y) \le 2m(n-1)$.
To get close to this upper bound in specific cases, we can take any $k$-vertex graph $H$, and add a path of length $n-k$ starting at a vertex $x \in V(H)$ and ending at a vertex $y$. Here, we have $R_G(x,y) = n-k$ and $T_G(y,x) = (n-k)^2$, so
$$
   T_G(x,y) = 2(|E(H)|+n-k)(n-k) - (n-k)^2.
$$
Even for this specific construction, we can do better by picking $x$ to be a vertex far from the start of the path; I will ignore this.
Your question is about graphs with at most $m$ edges; we can assume that $m$ is less than the number of edges in the extremal lollipop graph, or else we'd just take that graph. In this case, take $k = \frac23n$ and let $H$ be any graph with $m - \frac13n$ edges; we get
$$
   T_G(x,y) = \frac23 mn - \frac19 n^2 
$$
which is off from the upper bound by a constant factor. (To improve the constant a little, reduce $k$ to the least value such that $\binom k2 + n-k \ge m$.)
For planar graphs, the upper bound we get is $T_G(x,y) \le 2m(n-1) \le 6(n-1)(n-2)$. This is not too far off from the value $(n-1)^2$ we get in the case of a path. We can improve on the constant by taking $H$ to be a $k$-vertex triangulation; then we have $$T_G(x,y) = 2(n+2k-6)(n-k) - (n-k)^2 = (n+5k-12)(n-k).$$ This is maximized when $k = \frac25(n+3)$, giving us a graph that contains a hitting time of $T_G(x,y) = \frac95(n-2)^2$. Even this constant is probably not the best possible.
For grid mazes, we can do something similar, taking a large block with as few walls as you're willing to allow, and adding a long path coming out of a corner of that block.
