A graph is 4-regular if all its vertices are of degree 4. It is class 1 if the set of edges of the graph can be partitioned into perfect matchings; alternatively, if it can be edge-4-colored. A subgraph of a graph $G$ is spanning if it contains all the vertices of $G$. A graph is hamiltonian if it has a circuit containing all its vertices.
I have two questions:
Question 1 Is it possible to provide an example of a non-hamiltonian, connected, class 1, 4-regular graph?
And
Question 2 If a class 1, connected, 4-regular graph $G$ has a class 1, 3-regular connected spanning subgraph $S$, is $G$ Hamiltonian? If so, is there a Hamilton circuit containing all the edges not in $S$?
Best Answer
The graph from here, found via a House of Graphs search and also pictured below, is $4$-regular, connected, and class $1$ (as the edge coloring shows), but not Hamiltonian:
Also, $3$-regular graph formed by the orange, black, and purple edges in the coloring above is connected, so this means that the answer is "no" to both of your questions.