[proofplan]
The strategy is to build $\tilde{f}$ as a pointwise infimum over $E$ of the affine "cones" $y \mapsto f(y) + L|x - y|$. Three checks are needed: (i) the infimum is finite, (ii) $\tilde{f}|_E = f$, and (iii) $\tilde{f}$ is $L$-Lipschitz on $\mathbb{R}^n$. The first two follow from the Lipschitz bound on $f$ applied directly; the third follows from a triangle-inequality estimate that compares the minimising cones at two points $x_1, x_2 \in \mathbb{R}^n$. The construction for $\hat{f}$ is symmetric (replace cones by their reflections). Finally, the bound $\operatorname{Lip}(\tilde{f}) \le L$ is sharp because $\tilde{f}$ extends an $L$-Lipschitz function.
[/proofplan]
[step:Define the candidate extension and verify its values are finite]
Fix $x \in \mathbb{R}^n$. For each $y \in E$, define
\begin{align*}
g_y : \mathbb{R}^n &\to \mathbb{R} \\
x &\mapsto f(y) + L|x - y|,
\end{align*}
so that $\tilde{f}(x) = \inf_{y \in E} g_y(x)$. We must show $\tilde{f}(x) > -\infty$.
Fix any reference point $y_0 \in E$ (which exists since $E$ is non-empty). For every $y \in E$, the Lipschitz bound on $f$ gives
\begin{align*}
f(y) \ge f(y_0) - L|y - y_0|,
\end{align*}
hence
\begin{align*}
g_y(x) = f(y) + L|x - y| \ge f(y_0) - L|y - y_0| + L|x - y| \ge f(y_0) - L|x - y_0|,
\end{align*}
where the last step uses the triangle inequality $|y - y_0| \le |x - y| + |x - y_0|$. Taking the infimum over $y \in E$,
\begin{align*}
\tilde{f}(x) \ge f(y_0) - L|x - y_0| > -\infty.
\end{align*}
On the other hand, choosing $y = y_0$ in the infimum gives the upper bound $\tilde{f}(x) \le f(y_0) + L|x - y_0| < \infty$. Therefore $\tilde{f}(x) \in \mathbb{R}$ for every $x \in \mathbb{R}^n$.
[/step]
[step:Verify that $\tilde{f}$ extends $f$ on $E$]
Fix $x \in E$. Choosing $y = x$ in the definition gives
\begin{align*}
\tilde{f}(x) \le g_x(x) = f(x) + L \cdot 0 = f(x).
\end{align*}
Conversely, for every $y \in E$, the $L$-Lipschitz bound on $f|_E$ gives
\begin{align*}
f(x) - f(y) \le L|x - y|, \qquad \text{i.e.,} \qquad f(x) \le f(y) + L|x - y| = g_y(x).
\end{align*}
Taking the infimum over $y \in E$ yields $f(x) \le \tilde{f}(x)$. Combining,
\begin{align*}
\tilde{f}(x) = f(x) \quad \text{for all } x \in E.
\end{align*}
[/step]
[step:Show $\tilde{f}$ is $L$-Lipschitz on $\mathbb{R}^n$]
Fix $x_1, x_2 \in \mathbb{R}^n$. We show $\tilde{f}(x_1) - \tilde{f}(x_2) \le L|x_1 - x_2|$; the reverse inequality follows by symmetry.
Let $\varepsilon > 0$. By the definition of $\tilde{f}(x_2)$ as an infimum, there exists $y_\varepsilon \in E$ with
\begin{align*}
g_{y_\varepsilon}(x_2) = f(y_\varepsilon) + L|x_2 - y_\varepsilon| < \tilde{f}(x_2) + \varepsilon.
\end{align*}
By the triangle inequality $|x_1 - y_\varepsilon| \le |x_1 - x_2| + |x_2 - y_\varepsilon|$, hence
\begin{align*}
\tilde{f}(x_1) \le g_{y_\varepsilon}(x_1) &= f(y_\varepsilon) + L|x_1 - y_\varepsilon| \\
&\le f(y_\varepsilon) + L|x_2 - y_\varepsilon| + L|x_1 - x_2| \\
&= g_{y_\varepsilon}(x_2) + L|x_1 - x_2| \\
&< \tilde{f}(x_2) + L|x_1 - x_2| + \varepsilon.
\end{align*}
Since $\varepsilon > 0$ was arbitrary,
\begin{align*}
\tilde{f}(x_1) - \tilde{f}(x_2) \le L|x_1 - x_2|.
\end{align*}
Swapping the roles of $x_1$ and $x_2$ gives the reverse inequality, so $\tilde{f}$ is $L$-Lipschitz on $\mathbb{R}^n$.
[/step]
[step:Conclude $\operatorname{Lip}(\tilde{f}) = L$ and address the symmetric construction]
The previous step gives $\operatorname{Lip}(\tilde{f}) \le L$. For the reverse inequality, observe that $\tilde{f}|_E = f$ has Lipschitz constant exactly $L$ (assuming $L$ is the optimal Lipschitz constant of $f$); restriction can only decrease the Lipschitz constant, so $\operatorname{Lip}(\tilde{f}) \ge \operatorname{Lip}(\tilde{f}|_E) = \operatorname{Lip}(f) = L$. Hence $\operatorname{Lip}(\tilde{f}) = L$.
For the symmetric construction, define
\begin{align*}
\hat{f} : \mathbb{R}^n &\to \mathbb{R} \\
x &\mapsto \sup_{y \in E} \bigl( f(y) - L|x - y| \bigr).
\end{align*}
Setting $h := -f$, $h$ is $L$-Lipschitz on $E$, and the formula for $\hat{f}$ becomes $\hat{f}(x) = -\inf_{y \in E}(h(y) + L|x-y|)$. Applying the result already established to $h$ produces an $L$-Lipschitz extension $\tilde{h}: \mathbb{R}^n \to \mathbb{R}$ of $h$, and $\hat{f} = -\tilde{h}$ is therefore an $L$-Lipschitz extension of $f$ to all of $\mathbb{R}^n$.
[/step]
