Class 1, 4-regular graphs

139 Views Asked by At

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

1

There are 1 best solutions below

1
On 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:

enter image description here

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.