3
$\begingroup$

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

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you! This is quite amazing! $\endgroup$
    – EGME
    Nov 23, 2019 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.