A graph $G$ is Hamiltonian if there is a [Hamiltonian cycle](https://mathworld.wolfram.com/HamiltonianCycle.html) in $G$.
Suppose $G$ is a [$k$-edge connected](https://en.wikipedia.org/wiki/K-edge-connected_graph) $k$-regular graph with $k>1$.
Does this ensure that $G$ is Hamiltonian?


If not, how about [vertex-transitive](https://en.wikipedia.org/wiki/Vertex-transitive_graph) $k$-regular graphs? (we know that vertex-transitive $k$-regular graphs are $k$-edge connected). We also know that $k$-regular hypercubes admit a Hamiltonian cycle (called Gray codes).



Is every $k$-edge connected $k$-regular graph Hamiltonian?
Assume $k \geq 4$, since, for $k=2$, the answer for both questions is **yes**, and for $k=3$, **no**, as there's the [Petersen graph](https://en.wikipedia.org/wiki/Petersen_graph).


The answer to the first question is **no**. To see this, we only need to prove that the constructions by Meredith in [1] give $k$-edge-connected graphs, as Meredith already proved that the graph is non-Hamiltonian and regular.


Let's recall Meredith's construction. Let $n,m$ be integers, $n=m+\alpha$, where $\alpha \in \{ -1,0,1\}$ such that $2m+n=k$. Take a Petersen graph $P$ and label the vertices $A, B, \cdots , J$, such that the edges are


* $AB,CD,EF,GH,IJ$;
* $AC,CE,EG,GI,IA$;
* $BF,FJ,JD,DH,HB$.


Then the $k$-regular Meredith graph $M\_k$ consists of vertices $X\_1,\cdots,X\_{k-1},x\_{11},\cdots,x\_{1n},x\_{21},\cdots,x\_{2m},x\_{31},\cdots,x\_{3m}$ (call them "vertices of type $X$") where $X$ denotes a letter in $\{A,B,C,D,E,F,G,H,I,J\}$ and $x$ the respective lowercase letter.


The edges are


* $X\_px\_{qr}$ where $X$ is a letter and $x$ its respective lowercase letter, and $p,q,r$ arbitrary;
* $x\_{1p}y\_{1p}$ where $xy \in \{ab,cd,ef,gh,ij\}$ and $p$ arbitrary;
* $x\_{2p}y\_{3p}$ where $xy \in \{ac,ce,eg,gi,ia\}$ and $p$ arbitrary;
* $x\_{3p}y\_{2p}$ where $xy \in \{bf,fj,jd,dh,hb\}$ and $p$ arbitrary;


[Wikipedia](https://en.wikipedia.org/wiki/Meredith_graph) contains some descriptions for $M\_4$.


Now we proof that $M\_k$ is $k$-connected. Let $\bar{M}\_k$ be a graph formed by removing $k-1$ edges from $M\_k$. We proceed to prove that $\bar{M}\_k$ is connected.


If the removal disconnects the subgraph induced by the vertices of type $X$ for some $X$, then the removed vertices must share some $x\_{qr}$ as an endpoint, since the induced subgraph is isomorphic to $K\_{k,k-1}$. But now we can check the structure of $\bar{M}\_k$ and discover that it's connected.


If the removal keeps connected the subgraphs induced by the vertices of type $X$ for all $X$, then we only need to ensure that the subgraphs are connected "in between". That is, we construct a subgraph $Q$ of $P$, where two vertices $M,N$ of $P$ are connected if and only if there's at least one edge between a vertex of type $M$ and a vertex of type $N$ in $\bar{M}\_k$. If $Q$ is connected, then $\bar{M}\_k$ is connected.


To see that $Q$ is connected, we recall that removing $3$ edges can only disconnect the Petersen graph into a vertex and the remaining subgraph; any other disconnection requires at least $4$ edges. Either way, there must be at least $k$ edges disconnected in $M\_k$ to make $Q$ disconnected.


So we have proven that $\bar{M}\_k$ is connected, and thus $M\_k$ is $k$-connected.


Lovasz [conjectured](https://en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture) that every finite connected vertex-transitive graph contains a Hamiltonian cycle except five known counterexamples, i.e. $K\_2$, the Petersen graph, the Coxeter graph, and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle. All of them have vertex degree $\leq 3$. As the conjecture is neither proven or refuted, we can say that the answer to the second question is **unknown**.


[1] Meredith, G. H. J. (1973). Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs. Journal of Combinatorial Theory, Series B, 14(1), 55-60.


