Let $X_t$ and $Y_t$ be independent continuous time random walks on the same connected undirected finite graph $G=(V,E)$. The meeting time $T$ is defined as $T:=\inf\{t>0:X_t=Y_t,X_{t-}\neq Y_{t-}\}$. I would like to have a lower bound on $\min_{x\in V}E[T|X_0=Y_0=x]$, as a function of the number of vertices $n=|V|$, and the maximal degree $d$. For fixed $d$, I’m hoping for the bound to be linear in $n$.

Specifically, the continuous time random walk is defined by associating i.i.d. Poisson clocks to the vertices. Each time the clock rings the random walk steps to a uniformly random neighbor of the current vertex.