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

  • $\begingroup$ It would be nice if the question included the somewhat obscure definition of a $4$-ordered Hamiltonian graph (for context). $\endgroup$ – Misha Lavrov Dec 6 '17 at 4:26
  • $\begingroup$ @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. $\endgroup$ – Morteza Soltani Dec 6 '17 at 4:33
  • $\begingroup$ Thanks! I've moved this definition into the question, because nobody ever reads comments :) $\endgroup$ – Misha Lavrov Dec 6 '17 at 4:39
  • $\begingroup$ @MishaLavrov Thanks a lot! $\endgroup$ – Morteza Soltani Dec 6 '17 at 4:54
  • $\begingroup$ @MishaLavrov As promised I am sharing the solution that I have come up with right here :) $\endgroup$ – 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.)

  • $\begingroup$ 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. $\endgroup$ – Morteza Soltani Dec 6 '17 at 4:53
  • $\begingroup$ Try looking at graphs with a small vertex cut. $\endgroup$ – Misha Lavrov Dec 6 '17 at 5:03
  • $\begingroup$ Thanks for the hint. I try to do so and If I could get it, I will share it right here :) $\endgroup$ – Morteza Soltani Dec 6 '17 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.