[Math] Is it possible disconnected graph has euler circuit

eulerian-pathgraph theory

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?

Best Answer

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

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

[Math] Connected graphs, Euler circuits and paths, vertices of odd degree

TheHint for question 1:

$(\text{Euler circuit} \Rightarrow \text{ even degrees})$ Direct the circuit, prove that for any vertex we have the in-degree equal to the out-degree, hence their sum must be even.
$(\text{Euler circuit} \Leftarrow \text{even degrees})$ One of many possible ways is to use induction on the number of edges.
1. Find any cycle $C$.
2. If it is an Euler circuit, you are done.
3. If it is not, remove it from the graph (the remaining part has fever edges and still even degrees).
4. Process each connected component separately to obtain an Euler circuit for it (we can because of inductive hypothesis).
5. Merge the circuits using cycle $C$.

Hint for question 2:

If you have two vertices of odd degrees, you can add a new vertex which is adjacent to both of them.
If you have an Euler path, you can add a new vertex and make it an Euler cycle.

I hope this helps $\ddot\smile$

Best Answer

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

[Math] Connected graphs, Euler circuits and paths, vertices of odd degree

Related Question