1
$\begingroup$

All graphs to be considered are simple. A graph is matching covered if every edge of the graph belongs to a perfect matching of the graph. A graph is class 1 if it is edge 4-colorable. A graph is Hamiltonian if it has a circuit containing all its vertices. A graph is 4-regular if all its vertices have degree 4. A graph is of even order if it has an even number of vertices

I have the following question:

Question 1 Is a 4-regular, Hamiltonian graph of even order matching covered necessarily? Is there a counterexample?

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Here is a counterexample:

enter image description here

We've got a $4$-regular, Hamiltonian graph on $12$ vertices. However, deleting the highlighted edge leaves two components on $5$ vertices, which don't have a perfect matching, so the highlighted edge is not part of any matching.

$\endgroup$
1
  • $\begingroup$ Thank you again! $\endgroup$
    – EGME
    Commented Nov 23, 2019 at 16:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .