Is every $k$-edge connected $k$-regular graph Hamiltonian? A graph $G$ is Hamiltonian if there is a Hamiltonian cycle in $G$.
Suppose $G$ is a $k$-edge connected $k$-regular graph with $k>1$.
Does this ensure that $G$ is Hamiltonian?
If not, how about vertex-transitive $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).
 A: 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.
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_{2p}$ where $xy \in \{ac,ce,eg,gi,ia\}$ and $p$ arbitrary;


*$x_{3p}y_{3p}$ where $xy \in \{bf,fj,jd,dh,hb\}$ and $p$ arbitrary;
Wikipedia 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 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.
