On 4-ordered Hamiltonian Graphs I am trying to solve the following problem:

Let $G$ be a graph of order $n\geq 4$ such that deg $v \geq n/2$ for every vertex $v$ of $G$. Show that $G$ need not be 4-ordered Hamiltonian.

Here, a graph $G$ of order $n$ is $k$-ordered Hamiltonian for an integer $1 \le k \le n$ if for every ordered set $S={v_1,v_2,\dots,v_k}$ of $k$ vertices of $G$, there is a Hamiltonian cycle of $G$ encountering these $k$ vertices of $S$ in the order listed. 
Here is my solution! Please let me know if this solution is not correct or does not reflect a general case:
Assume $G$ be the join of graphs $2\,K_{\frac{n-2}{2}}$ and $K_2$, i.e., $G = 2\, K_{\frac{n-2}{2}}\vee K_2$. Let $X$ and $Y$ be two sets of vertices with $\lvert X\rvert = \lvert Y\rvert = \frac{n-2}{2}$ and let $Z$ denote the set that contains the rest of the vertices of $G$. Clearly, every vertex $v$ of $G$ has degree deg $v \geq n/2$. Therefore, by Dirac's Theorem, $G$ is Hamiltonian. 
To see that $G$ is not 4-ordered Hamiltonian, consider the sequence $v_1,\,v_2,\,v_3,\,v_4$ of distinct vertices of $G$, where $v_i \in X$ if $i$ is odd and $v_i \in Y$ if $i$ is even, for every $1\leq i\leq 4$. 
Suppose, to the contrary, that $G$ is 4-ordered Hamiltonian. Then there exists a Hamiltonian cycle $C$ in $G$ that encounters the vertices $v_1,\,v_2,\,v_3,\,v_4$ in the considered order. Furthermore, since $C$ is a Hamiltonian cycle, it can be decomposed into 4 internally disjoint paths $P_1,\,P_2,\,P_3,\,P_4$ where $P_i$ is a $v_i-v_{i+1}$ path for $i=1,\,2,\,3$ and $P_4$ is a $v_4-v_1$ path. Observe that for each odd integer $j\,(1\leq j\leq 4)$, the vertex $v_j$ is in $X$ and is only adjacent to vertices in $Z$. Hence, each path $P_i\,(1\leq i\leq 4)$ must contain at least one vertex of $Z$. This implies that $\lvert Z\rvert \geq 4$, but $\lvert Z\rvert = 2$. Hence, we reach a contradiction and thus $G$ is not 4-ordered Hamiltonian.
Note that, although in this problem $k = 4$, it can be generalized to any value of $k$ such that $1\leq k\leq n$.
 A: To show that $G$ "need not be" $4$-ordered Hamiltonian, a single counter-example is enough.
The trouble is that when $n\ge 6$, $K_{n/2,n/2}$ is in fact $4$-ordered Hamiltonian: for any four vertices $v_1, v_2, v_3, v_4$, there is a Hamiltonian cycle containing those vertices in that order.
(In fact, $K_{3,3}$ was pointed out as an example of a $4$-ordered Hamiltonian graph in the original paper of Ng and Schultz defining them. From there, it is not hard to see that all larger $K_{n,n}$ are $4$-ordered Hamiltonian: the only case that cannot occur in $K_{3,3}$ is when all four vertices are on one side of the bipartition, and finding a Hamiltonian cycle visiting those vertices in any order is easy.)
It's technically true that $K_{2,2}$ is a counter-example: it has $n \ge 4$ and $\deg v \ge 2$ for all $v$, but there is only one cyclic order in which the vertices can be visited, because there is only one cycle. But I assume that the question did not intentionally allow this case, because it seems trivial. 
(I would personally not be satisfied until I had a counter-example for arbitrarily large $n$, but the question does not ask for that.)
