0
$\begingroup$

Is $G$ a graph which has an isolated vertex and its other connected component is $C_{45}$ an Eulerian graph? To be an Eulerian graph, could it happen that our graph is not connected?

$\endgroup$
1
  • 1
    $\begingroup$ As far as I know, the definition of Eulerian means that the cycle hits every edge once, so the cycle need not be spanning. You're probably confusing Eulerian with Hamiltonian. $\endgroup$
    – koifish
    Commented Dec 13, 2023 at 3:54

1 Answer 1

Reset to default
1
$\begingroup$

The answer depends on exact definition of Eulerian graph. It may vary for different authors.

Euler himself didn't mention any connectivity at all, even in the theorem. In the problem with bridges connectivity could look like something natural. On the other hand isolated island would be also natural. Euler couldn't know in advance that his article would become the first article in graph theory, so he didn't care much about such details.

The definition in Graph theory with applications by Bondy and Murty doesn't mention connectivity. (In this case an extra isolated vertex is allowed.) enter image description here

Another definition you can find, e. g. in Exercises in Graph Theory by Melnikov et al. It is not so popular, however sometimes occurs. enter image description here

There is also a rather different point of view on what to call an Eulerian graph (or Euler graph), e. g. in Linear Graphs and Electrical Networks by Seshu and Reed. enter image description here

So if you are solving a problem read the definition given in the same book or in lectures. If you create a new material I would recommend using the first definition as the most relevant.

$\endgroup$

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