The first approach can be formalized as follows.
Let $P$ be an arbitrary set of $n$ points on the positive branch of the parabola $y=x^2$; that is,
$$
P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}
$$
for some positive real numbers $t_1, t_2, \dots, t_n$. Without loss of generality, assume these points are indexed in increasing order: $0 < t_1 < t_2 < \cdots < t_n$.
Claim: In the Delaunay triangulation of $P$, the leftmost point $(t_1, t_1^2)$ is a neighbor of every other point in $P$.
This claim implies that adding a new point $(t_0, t_0^2)$ to $P$ with $0 < t_0 < t_1$ adds $n$ new edges to the Delaunay triangulation. Thus, inductively, if we incrementally contract the Delaunay triangulation of $P$ by inserting the points in right-to-left order, the total number of Delaunay edges created is $\Omega(n^2)$.
We can prove the claim as follows. For any real values $0<a<b<c$, let $C(a,b,c)$ denote the unique circle through the points $(a,a^2), (b,b^2), (c,c^2)$.
Lemma: $C(a,b,c)$ does not contain any point $(t,t^2)$ where $a<t<b$ or $c<t$.
Proof: Recall that four points $(a,b), (c,d), (e,f), (g,h)$ are cocircular if and only if
$$
\begin{vmatrix}
1 & a & b & a^2 + b^2 \\
1 & c & d & c^2 + d^2 \\
1 & e & f & e^2 + f^2 \\
1 & g & h & g^2 + h^2 \\
\end{vmatrix}
=
0
$$
Thus, a point $(t,t^2)$ lies on the circle $C(a,b,c)$ if and only if
$$
\begin{vmatrix}
1 & a & a^2 & a^2 + a^4 \\
1 & b & b^2 & b^2 + b^4 \\
1 & c & c^2 & c^2 + c^4 \\
1 & t & t^2 & t^2 + t^4 \\
\end{vmatrix}
=
0
$$
It's not hard (for example, ask Wolfram Alpha) to expand and factor the $4\times4$ determinant into the following form:
$$
(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0
\tag{$*$}
$$
Thus, $(t,t^2)$ lies on $C(a,b,c)$ if and only if $t=a$, $t=b$, $t=c$, or $t=-a-b-c < 0$. Moreover, because $0<a<b<c$, these four roots are distinct, which implies that the parabola actually crosses $C(a,b,c)$ at those four points. It follows that $(t,t^2)$ lies inside $C(a,b,c)$ if and only if $-a-b-c<t<a$ or $b<t<c$.$\qquad\Box$
