This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and Ottolini. We have no particular reason to think the inequality is true except that it would fit very naturally into our other results and seems naturally related to some existing results.

Spectral Version. Suppose $G=(V,E)$ is a finite, connected graph on $n$ vertices and $L=D-A$ is the associated (Kirchhoff) Graph Laplacian. $L$ has eigenvalues $ 0 = \lambda_1 < \lambda_2 \leq \lambda_3 \leq \dots$

Question. Is it true that, for some universal constant $c>0$, that $$ \mbox{diam}(G)^2 \leq c \sum_{i=2}^{n} \frac{1}{\lambda_i} \qquad ?$$

The right-hand side is also sometimes known as the Kirchhoff index of a graph but we couldn't find the inequality in the literature. The inequality would be sharp up to constants for the cycle graph $C_n$ in the sense that both sides are $\sim n^2$. There's a related inequality of Alon-Milman saying that, with $\Delta$ being the largest degree, that $$ \mbox{diam}(G)^2 \leq c \cdot \Delta \cdot (\log n)^2 \cdot \frac{1}{\lambda_2}$$ and one way of phrasing our question is whether one can remove the dependence on $|V| = n$ and $\Delta$ by taking the remainder of the spectrum into account. We also note that there is an inequality by McKay that can be written as $$ \mbox{diam}(G) \geq \frac{4}{n} \frac{1}{\lambda_2} \geq \sum_{i=2}^{n} \frac{1}{\lambda_i}$$ where the second inequality is of course quite suboptimal, however, it does naturally suggest the question of whether there is a converse statement along these lines.

Random Walk Version A way of phrasing the question probabilistically is as follows: define the commute time $C_{ij}$ between two vertices $i,j \in V$ as the expected time a random walk needs to go from $i$ to $j$ and then return to $i$. Note that this definition is symmetric $C_{ij} = C_{ji}$.

Question. Is there a universal $c>0$ such that $$ \mbox{average commute time} = \frac{1}{n^2} \sum_{i,j \in V} C_{ij} \geq c \frac{ \mbox{diam}(G)^2 \cdot |E|}{|V|}.$$

This seems like a really nice inequality: in order for random walks to travel quickly between a `typical' pair of vertices we want small diameter and few edges. It's easy to see that for a cycle graph $C_n$ both sides are $\sim n^2$. If we take an expander graph on $n$ vertices, then one would expect the left-hand side to be $\sim n$ while the right-hand side is $\sim 1$ (since $|E| \sim |V|$ and $\mbox{diam}(G) \sim 1$), so the inequality would be far from sharp in that case.

One way of showing the equivalence between the two formulations is as follows. Define the resistance distance between two vertices as $ \Omega_{ij} = C_{ij}/(2|E|).$ Using the identity $ \frac{1}{n} \sum_{i < j \in V} \Omega_{i,j} = \sum_{i=2}^{n} \frac{1}{\lambda_i}$ and we can rewrite our question as $$ \mbox{diam}(G)^2 \leq c \sum_{i=2}^{n} \frac{1}{\lambda_i} = \frac{c}{n} \sum_{i < j \in V} \Omega_{i,j} = \frac{c}{2|E| n} \sum_{i <j} C_{ij}.$$

This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and Ottolini. We have no particular reason to think the inequality is true except that it would fit very naturally into our other results and seems naturally related to some existing results.

Spectral version. Suppose $G=(V,E)$ is a finite, connected graph on $n$ vertices and $L=D-A$ is the associated (Kirchhoff) Graph Laplacian. $L$ has eigenvalues $ 0 = \lambda_1 < \lambda_2 \leq \lambda_3 \leq \dots$

Question. Is it true that, for some universal constant $c>0$, that $$ \mbox{diam}(G)^2 \leq c \sum_{i=2}^{n} \frac{1}{\lambda_i} \qquad ?$$

The right-hand side is also sometimes known as the Kirchhoff index of a graph but we couldn't find the inequality in the literature. The inequality would be sharp up to constants for the cycle graph $C_n$ in the sense that both sides are $\sim n^2$. There's a related inequality of Alon-Milman saying that, with $\Delta$ being the largest degree, that $$ \mbox{diam}(G)^2 \leq c \cdot \Delta \cdot (\log n)^2 \cdot \frac{1}{\lambda_2}$$ and one way of phrasing our question is whether one can remove the dependence on $|V| = n$ and $\Delta$ by taking the remainder of the spectrum into account. We also note that there is an inequality by McKay that can be written as $$ \mbox{diam}(G) \geq \frac{4}{n} \frac{1}{\lambda_2} \geq \sum_{i=2}^{n} \frac{1}{\lambda_i}$$ where the second inequality is of course quite suboptimal, however, it does naturally suggest the question of whether there is a converse statement along these lines.

Random walk version. A way of phrasing the question probabilistically is as follows: define the commute time $C_{ij}$ between two vertices $i,j \in V$ as the expected time a random walk needs to go from $i$ to $j$ and then return to $i$. Note that this definition is symmetric $C_{ij} = C_{ji}$.

Question. Is there a universal $c>0$ such that $$ \mbox{average commute time} = \frac{1}{n^2} \sum_{i,j \in V} C_{ij} \geq c \frac{ \mbox{diam}(G)^2 \cdot |E|}{|V|}.$$

This seems like a really nice inequality: in order for random walks to travel quickly between a `typical' pair of vertices we want small diameter and few edges. It's easy to see that for a cycle graph $C_n$ both sides are $\sim n^2$. If we take an expander graph on $n$ vertices, then one would expect the left-hand side to be $\sim n$ while the right-hand side is $\sim 1$ (since $|E| \sim |V|$ and $\mbox{diam}(G) \sim 1$), so the inequality would be far from sharp in that case.

One way of showing the equivalence between the two formulations is as follows. Define the resistance distance between two vertices as $ \Omega_{ij} = C_{ij}/(2|E|).$ Using the identity $ \frac{1}{n} \sum_{i < j \in V} \Omega_{i,j} = \sum_{i=2}^{n} \frac{1}{\lambda_i}$ and we can rewrite our question as $$ \mbox{diam}(G)^2 \leq c \sum_{i=2}^{n} \frac{1}{\lambda_i} = \frac{c}{n} \sum_{i < j \in V} \Omega_{i,j} = \frac{c}{2|E| n} \sum_{i <j} C_{ij}.$$