Let $(G_n)_{n \geq 1}$ be a graph sequence that has a bounded degree, i.e., $\max_{v \in [n]}d_v = d_{\max} \leq K$ and $G_n$ is connected for every $n \geq 1$. Let $[n]$ be the set of vertices of $G_n$.
To show: For all $\varepsilon > 0$, $$ \lim_{n \to \infty}\mathbb{P}(H_n \leq (1-\varepsilon)\log n/\log d_{\max}) = 0. $$ The random variable $H_n$ is a typical distance. Draw two vertices $U_1$ and $U_2$ uniformly at random. Then $H_n = \operatorname{dist}_{G_n}(U_1, U_2)$, where the operator $\operatorname{dist}_{G_n}$ measures the shortest distance between $U_1$ and $U_2$ in graph $G_n$.
My attempt: Well not much since I don't know how to analyse this event. The random variable $H_n < \infty$ a.s. for all $n \geq 1$ because $G_n$ is connected. Using the definition of $H_n$: $$ \mathbb{P}(H_n \leq (1-\varepsilon)\log n/\log d_{\max}) = \mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) \leq (1-\varepsilon)\log n/\log d_{\max}). $$ Let $k_n := \lceil (1-\varepsilon)\log n/\log d_{\max} \rceil$. Then $$ \mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) \leq k_n) = \sum_{k = 0}^{k_n}\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k). $$ So now, what is $\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k)$ for $0 \leq k \leq k_n$? I was thinking \begin{align*} \mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k) &= \sum_{u,v \in [n]}\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k|U_1 = u, U_2 = v)\mathbb{P}(U_1 = u, U_2 = v)\\ &= \frac{1}{n^2}\sum_{u,v \in [n]}\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = k|U_1 = u, U_2 = v) \end{align*} If $k = 0$, then $\mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = 0|U_1 = u, U_2 = v) = 1$ if and only if $u = v$, otherwise the probability is zero. So $$ \mathbb{P}(\operatorname{dist}_{G_n}(U_1, U_2) = 0) = \frac{1}{n^2}\sum_{u \in [n]}1 = \frac{n}{n^2} = \frac{1}{n}. $$ Great! But how about for other $k \neq 0$?
For any node $i \in [n]$ and distance $k$, there can be at most $d_\max^k$ nodes at distance $k$ from $i$. Hence
$$\mathbb P(H_n \le h) = \sum_{k=0}^{\lfloor h \rfloor} \mathbb P(H_n = k) \le \sum_{k=0}^{\lfloor h \rfloor} \frac{d_\max^k}{n} \le \frac{d_\max^{h+1} - 1}{n(d_\max - 1)},$$
where $d_\max > 1$ since the $G_n$ are connected. For $h = (1-\epsilon)\log(n)/\log(d_\max)$, the RHS tends to $0$.