1
$\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$
  • $\begingroup$ Note that wikipedia says that Eulerian graphs may be disconnected not that every disconnected graph is Eulerian... $\endgroup$ – Michael Biro Aug 30 '15 at 13:13
  • $\begingroup$ bliendly ,I beilieved that eluer graph must be connected . That's wrong. $\endgroup$ – Mithlesh Upadhyay Aug 30 '15 at 13:17
6
$\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$
  • $\begingroup$ That means , Any k-regular graph where k is an even number has euler circuit ? $\endgroup$ – Mithlesh Upadhyay Aug 30 '15 at 13:19
  • $\begingroup$ Suplimentay problem here $\endgroup$ – Mithlesh Upadhyay Aug 30 '15 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 Aug 30 '15 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 Aug 30 '15 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 Aug 30 '15 at 13:48

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.