Hamiltonian paths in same degree graph

Question

Suppose we have a connected graph, and all vertices of this graph have the same even degree.

Is it always true that this graph has a Hamiltonian path?

Furthermore, is it true if the degree $2k$, this graph can be split into $k$ Hamiltonian paths?

This problem is trivial for $k=1$ but I wonder if it also holds for $k>1$?

Answer 1

Let $G_1,\ldots,G_6$ be six copies of $K_7$. Consider the graph obtained by taking $G_1,\ldots,G_7$ and one "central" vertex $c$ and making the following changes to the edges.

• Label vertices $a_k,b_k$ in each $G_k$.
• Remove every edge $a_kb_k$.
• Connect every $a_k$ to $c$.
• Connect $b_1$ to $b_2$ and $b_3$ to $b_4$ and $b_5$ to $b_6$.

Sorry this is a bit obscure, and I am no good at posting pictures. But if you draw your own diagram I am sure you will see what I mean.

Then every vertex has degree $6$. In any path including all vertices we would have to have (without loss of generality) vertices in $G_1\cup G_2$; followed by $c$; followed by vertices in $G_3\cup G_4$; but then the only way to continue the path is to repeat $c$. So there is no Hamiltonian path.

Simpler example, inspired by Are all $4$-regular graphs Hamiltonian.

Take three copies $G_1,G_2,G_3$ of $K_7$, in each one remove an edge $a_kb_k$ and join both $a_k$ and $b_k$ to $c$.