1
$\begingroup$

I was given the above question in a test. I really struggle to see how it is possible that a Eulerian trail/path can fail to exist in a graph with all even degree vertices. When you consider that a Eulerian Cycle exists in any connected graph whose vertices are all of even degree, it makes it even more difficult to consider.

Is there an easy way to find such a graph or am I missing something? E.g. should I be considering, say, a graph consisting of disjoint sets of vertices, such as a graph of 8 vertices, with two sets of 4 vertices connected to make 2 disjoint squares (hence all vertices would have degree of 2)? Does this count? Any help appreciated!

$\endgroup$
1
  • 2
    $\begingroup$ "Does this count?" Of course, such graph will be the answer to your question! $\endgroup$
    – kabenyuk
    Commented May 5, 2022 at 3:02

1 Answer 1

Reset to default
1
$\begingroup$

Take any $\textbf{connected}$ graph $H$ that have all degrees being even and let $G$ be $H$ union an isomorphic copy of it. $G$ is the graph you want.

$\endgroup$

You must log in to answer this question.

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