# 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$.

• It would be nice if the question included the somewhat obscure definition of a $4$-ordered Hamiltonian graph (for context). – Misha Lavrov Dec 6 '17 at 4:26
• @MishaLavrov Thank you for your comment. Here is the definition of a 4-ordered Hamiltonian graph: A Hamiltonian graph $G$ of order $n$ is $k$-ordered Hamiltonian for an integer $k$ with $1\leq k \leq n$ if for every ordered set $S = \{v_1,v_2,\cdots,v_k\}$ of $k$ vertices of $G$, there is a Hamiltonian cycle of $G$ encountering these $k$ vertices of $S$ in the order listed. – Morteza Soltani Dec 6 '17 at 4:33
• Thanks! I've moved this definition into the question, because nobody ever reads comments :) – Misha Lavrov Dec 6 '17 at 4:39
• @MishaLavrov Thanks a lot! – Morteza Soltani Dec 6 '17 at 4:54
• @MishaLavrov As promised I am sharing the solution that I have come up with right here :) – Morteza Soltani Dec 6 '17 at 7:37

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.)

• Thanks for your prompt response. I now realized that $K_{n/2,n/2}$ can have all the possible combination of the set of four vertices of $G$ in the considered order. Although your counter example is nice and correct, I am trying to construct a generic Hamiltonian graph of order $n$ such that it is not 4-ordered Hamiltonian. – Morteza Soltani Dec 6 '17 at 4:53
• Try looking at graphs with a small vertex cut. – Misha Lavrov Dec 6 '17 at 5:03
• Thanks for the hint. I try to do so and If I could get it, I will share it right here :) – Morteza Soltani Dec 6 '17 at 5:36