This problem is easier than it seems at first reading. The main point is that we have two vertices $A_{999}$ and $A_{1000}$ with large degrees. So, whichever of these two vertices remains after deletion, it ensures that if the remaining graph is no more connected then one of its connected components is pretty large. So large that it prevents the possibility the remaining ones to form a graph with enough vertices to comply with the requirements. Solution. Consider the obvious graph interpretation with a corresponding graph $G$ with vertices $A_1,\dots,A_{1000}$ . Let $d:=d_{999}$. We get $$d_{999-d}\ge (999-d)+1=1000-d$$Since $d_{999}\le d$ it follows $1000-d\le d$ or $d\ge 500$. That is, $$d_{1000}\ge d_{999}=d\ge 500$$Suppose now, for the sake of contradiction, the graph is no more connected after deleting some vertex. Let $G_1,G_2,\dots,G_k$ be its connected components. Because either $A_{999}$ or $A_{1000}$ is not deleted, one of those connected components, say $G_j,$ has at least $d$ vertices (the worst case scenario is when one of $A_{999}, A_{1000}$ is deleted and they are connected). It means that $G':= \bigcup_{i\neq j}G_i$ has at most $999-d$ vertices. Let the vertices of $V(G')$ be $v_1,v_2,\dots,v_r, r\le 999-d$. It means $d_{G'}(v_j)\le r-1$, hence $$d_{G}(v_j)\le r, j=1,2,\dots,r\qquad (1)$$Since $r\le 999-d$ it yields $d_G(A_r)\ge r+1$ thus the only possible vertices in $G$ with degree less or equal to $r$ are $A_1,A_2,\dots,A_{r-1}$, i.e. their number is less than $r$. However, $(1)$ shows there are at least $r$ vertices with degree $r$ or less, contradiction.