  Approximating the graph diameter is a basic task of both theoretical and
practical interest. A simple folklore algorithm can output a 2-approximation to
the diameter in linear time by running BFS from an arbitrary vertex. It has
been open whether a better approximation is possible in near-linear time. A
series of papers on fine-grained complexity have led to strong hardness results
for diameter in directed graphs, culminating in a recent tradeoff curve
independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein,
STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for
any integer $k\ge 2$ and $\delta>0$, a $2-\frac{1}{k}-\delta$ approximation for
diameter in directed $m$-edge graphs requires $mn^{1+1/(k-1)-o(1)}$ time. In
particular, the simple linear time $2$-approximation algorithm is optimal for
directed graphs.
  In this paper we prove that the same tradeoff lower bound curve is possible
for undirected graphs as well, extending results of [Roditty and Vassilevska
W., STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of
the curve, $k=2,3$ and $4$, respectively. Our result shows in particular that
the simple linear time $2$-approximation algorithm is also optimal for
undirected graphs. To obtain our result we develop new tools for fine-grained
reductions that could be useful for proving SETH-based hardness for other
problems in undirected graphs related to distance computation.
