5
$\begingroup$

I have doubt !

Wikipedia says :

An Eulerian graph is one in which all vertices have even degree; Eulerian graphs may be disconnected.

What I know :

Defitition of an euler graph

"An Euler circuit is a circuit that uses every edge of a graph exactly once. ▶ An Euler path starts and ends at different vertices. ▶ An Euler circuit starts and ends at the same vertex."

According to my little knowledge "An eluler graph should be degree of all vertices is even, and should be connected graph".

I am asking :Is it possible disconnected graph has euler circuit ? If it is possible show an example .

EDITED : Here is my suplimentary problem , I voted for the anwser .

Which of the following graphs has an Eulerian circuit?

$\endgroup$
2
  • $\begingroup$ Note that wikipedia says that Eulerian graphs may be disconnected not that every disconnected graph is Eulerian... $\endgroup$
    – Michael Biro
    Commented Aug 30, 2015 at 13:13
  • $\begingroup$ bliendly ,I beilieved that eluer graph must be connected . That's wrong. $\endgroup$
    – Mithlesh Upadhyay
    Commented Aug 30, 2015 at 13:17

3 Answers 3

Reset to default
10
$\begingroup$

Here we go: $$\huge\cdot\qquad\cdot$$

remember that $0$ is even. The circuit is the "empty circuit"
Since the graph has no edges, we've already passed every edge if we don't even move :D

$\endgroup$
6
  • $\begingroup$ That means , Any k-regular graph where k is an even number has euler circuit ? $\endgroup$
    – Mithlesh Upadhyay
    Commented Aug 30, 2015 at 13:19
  • $\begingroup$ Suplimentay problem here $\endgroup$
    – Mithlesh Upadhyay
    Commented Aug 30, 2015 at 13:29
  • 1
    $\begingroup$ @user4791206 My bad, the wikipedia definition cited in your link was false. As such, not every $2n$-regular graph is eulerian and not every graph with even degrees is eulerian (see $\Delta\quad\Delta$). Instead, an eulerian graph can only be disconnected if there is exactly one connected component consisting of more than one vertex (i.e. all "disconnected vertices" must be singleton). $\endgroup$
    – AlexR
    Commented Aug 30, 2015 at 13:38
  • $\begingroup$ yes , What I concluded now , need verification A graph contains eluer circuit if graph is : (1) null graph , (2) With k-component , any only one component contains eluer circuit and other (k-1) have no edges .i.e. other is only vertices , (3) otherwise graph must be connected with euler circuit . $\endgroup$
    – Mithlesh Upadhyay
    Commented Aug 30, 2015 at 13:43
  • $\begingroup$ @user4791206 I think you might think the correct thing, but I can't quite verify because your english doesn't quite get it across. $\endgroup$
    – AlexR
    Commented Aug 30, 2015 at 13:48
1
$\begingroup$

The other answers answer your (misleading) title and miss the real point of your question.

Yes, a disconnected graph can have an Euler circuit. That's because an Euler circuit is only required to traverse every edge of the graph, it's not required to visit every vertex; so isolated vertices are not a problem. A graph is connected enough for an Euler circuit if all the edges belong to one and the same component.

But that's not what was confusing you five years ago when you asked the question. The confusion arises from the fact that some people use the term "Eulerian graph" to mean a graph that has an Euler circuit, while other people (deplorably) use the term "Eulerian graph" for any graph in which all vertices have even degree, regardless of whether or not it has a Eulerian circuit.

From the Wikipedia article Eulerian path:

The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.

People using the second definition would consider the graph $K_3\cup K_3$ to be "Eulerian", although of course it has no Euler circuit.

$\endgroup$
0
$\begingroup$

It's only possible for a disconnected graph to have an Eulerian path in the rather trivial case of a connected graph with zero or two odd-degree vertices plus vertices without any edges. An Eulerian path for the connected graph is also an Eulerian path for the graph with the added edge-free vertices (which clearly add no edges that need to be traversed). Whoop-te-doo! The whole issue seems pretty nit picky and pointless to me, though it appears to fascinate certain Wikipedia commenters.

$\endgroup$
8
  • $\begingroup$ That's not the issue. The issue is that some (bad) people give the name "Eulerian graph" to any graph in which every vertex has even degree. $\endgroup$
    – bof
    Commented Aug 18, 2020 at 7:05
  • $\begingroup$ Perhaps there are those who call a graph consisting entirely of even-degree vertices an "Eulerian graph," but the reference the Wikipedia claim cites to does not support that claim. It defines an Euler graph as "a graph in which every node has even degree." Euler, not an Eulerean graph. Euler has so many things named in his honor, that such distinctions matter. Euler's number is not Euler's constant. $\endgroup$
    – MJW
    Commented Aug 18, 2020 at 20:53
  • $\begingroup$ Maybe Euler's constant and "Euler's number" (and for that matter the Euler numbers) are not so easily confusable? Anyway, to me it would seem foolhardy and asking for trouble to use Euler graph and Eulerian graph for two different but related concepts. As far as I know the terms Euler circuit and Eulerian circuit are used interchangeably. I'm guessing the people who say "Euler circuit" will say "Euler graph" (whatever they mean by it) while those who say "Eulerian circuit" will say "Eulerian graph." $\endgroup$
    – bof
    Commented Aug 19, 2020 at 0:33
  • $\begingroup$ Euler's constant and Euler's number aren't easily confused, even though both are numbers and both are constants? Confusing though it may be -- and yea, even foolhardy -- Euler's number is the constant, e; Euler numbers are integers occurring in the coefficients of the Taylor series for 1/cosh(t); and Eulerain numbers count certain types of permutations. Those are all from Wikipedia. I've encountered other similar examples in the past, but don't off hand recall what they are. $\endgroup$
    – MJW
    Commented Aug 19, 2020 at 0:55
  • $\begingroup$ I'm saying the Wikipedia claim that the term "Eulerean graph" can refer to any graph with only even-degree vertices is unsupported unless there's a reference that calls such graphs Eulerean graphs. $\endgroup$
    – MJW
    Commented Aug 19, 2020 at 1:08

You must log in to answer this question.

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