# Show that $G$ is $3-$ordered Hamiltonian.

A Hamiltonian graph $G$ of order n is $k-$ordered Hamiltonian for an integer $k$ with $1≤k≤n$ if for every ordered set $S=\{v_1,v_2,…,v_k\}$ of $k$ vertices of $G$, there is a Hamiltonian cycle of $G$ encounter these $k$ vertices of $S$ in the order listed.

a) Let $G$ be a graph of order $n≥3$ such that $deg(v)≥\frac{n}{2}$ for every vertex $v$ of $G$. Show that $G$ is $3-$ordered Hamiltonian.

b) Let $G$ be a graph of order $n≥4$ such that $deg(v)≥\frac{n}{2}$ for every vertex $v$ of $G$. Show that $G$ need not be $4-$ordered Hamiltonian.

c) Show that if $G$ is 4-ordered Hamiltonian graph, then $G$ is 3-connected.

For both a) by Dirac's theorem, I know that $G$ is Hamiltonian, meaning $G$ has a cycle that go through every vertex of $G$. So Let $S=\{a,b,c\}$. We can find a cycle that goes through $S$ by following orders : $abc, acb, bca,bac, cab,cba$. So $G$ is 3-ordered Hamiltonian

for c), I'm still stuck

• 3-ordered Hamiltonian seems to be exactly the same as 'regular' Hamiltonian: for 3 elements you can start at 3 different places and walk in 2 different directions to get all possible permutations. – Leen Droogendijk Oct 26 '14 at 17:17
• thanks for your hint I can do part a) and b), but I still can't see the relationship between the 4-ordered Hamiltonian and 3-connected. – Diane Vanderwaif Oct 27 '14 at 13:05
• The concept of 'ordered Hamiltonian' is/was unknown to me. Nevertheless I would attempt to help if only you had specified part c in your question. Btw. your solution for part b is wrong. You have used a graph of order 8, but then the minimum degree must be 4. $C_8$ has minimum degree 2. – Leen Droogendijk Oct 27 '14 at 14:33
• sorry, I forgot to add part c), – Diane Vanderwaif Oct 27 '14 at 17:21
• Please do not forget to remove your incorrect "solution" for part b). – Leen Droogendijk Oct 27 '14 at 18:08

Note that for c) we need the additional requirement that $|G|>3$: $K_1$ certainly is 4-ordered Hamiltonian according to the given definition, but it is not 3-connected.
Suppose $G$ is not 3-connected. Then it has a vertex cut of size 2, say $\{x,y\}$. Suppose this vertex cut separates vertices $a$ and $b$. Because $G$ is 4-ordered Hamilton, there is a cycle in $G$ that contains the vertices $a,x,y,b$ in this sequence. Now by walking from $a$ to $b$ along this cycle, using the path that avoids $x$ and $y$ we have exhibited an $a,b$-path in $G-\{x,y\}$. Contradiction.