# Class 1, 4-regular graphs

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$$?

• Certainly a disconnected graph. lol, I'll think about it and get back Nov 22, 2019 at 22:18
• @oshill Thank you, I edited the question ... need to think more carefully about the edits, but now is kind of late for me ..
– EGME
Nov 22, 2019 at 22:22

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.