Olympiad Graph Problem

So we know that there must be some path containing all but one vertex, call the vertices on such a path $P = v_1, v_2, \ldots, v_{n-1}$, and let $u$ be the last vertex. I suggest going on like this.

Consider first the case when $v_1v_{n-1} \in E$, you should be able to check that $E[\{u\}, V(P)] = \emptyset$. Then suppose that $vw \notin E$ for distinct $v,w \in V(P)$. Prove that $v$ and $w$ cover every vertex. Otherwise $V(P)$ is a clique and we are done.

It remains to study the case when $v_1v_{n-1} \notin E$. Check that for $x \in \{v_2,\ldots,v_{n-2}\}$, if $ux \notin E$, then $sx,xt \in E$. From this, $E[\{u\},V(P)] = \emptyset$, we get that $s$ and $t$ cover every vertex. So we may assume there is some $v_i$ with $2 \leq i \leq n-2$ with $uv_i \in E$. Take $i$ minimum and proceed in two cases, whether $i=2$ or not.

There are many details to check, but none is harder than the proof that you can assume that there is a path of length 99.