self doubt closed

Question

Both euler path and euler circuit can be present in a graph ?

Answer 1

Answer : Yes 

Disclaimer  : Before you read my explanations , I found some resources out on internet which have different definitions for what a Eulerian Circuit and Eulerian Path is… like this and this… I won’t argue the reliability of those sources. The following answer is coherent with Definitions present on wikipedia. 

Eulerian path is a trail in graph that visits every edge exactly once.

Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.

$\therefore$ Every Eulerian Circuit is also an Eulerian path. So any graph that has Eulerian Circuit has Eulerian Paths.

The converse may not be True , means Even if a graph has an Eulerian Path , Eulerian Circuit is not guaranteed to exist.

Furthermore following points are true irrespective of source of information :

1. Connected graph with every vertex with even degree is both necessary and sufficient condition for Eulerian Circuit.

2. Connected graph with exactly 2 vertices with odd degree have Eulerian Path but not an Eulerian Circuit.

3. Anything Else neither have Eulerian Path nor Eulerian Circuit.

Example :

1.  

In above graph the trail $V_1E_1V_2E_2V_3E_3V_4E_4V_5E_5V_1$ is both an Eulerian Path as well as Eulerian Circuit. As it visits all edges and starts and ends on same vertex .

Now if any one of the $5$ edge was absent like in example below :

2.  

In above graph vertex $V_1$ and $V_5$ are only two vertices with odd degree so  the trail $V_1E_1V_2E_2V_3E_3V_4E_4V_5$ is an Eulerian Path and there is no Eulerian Circuit.

In such graphs the Eulerian Path starts on one of the odd degree vertex and ends on the other odd degree vertex.

Comments

Means for path it is not necessary to have different starting ending vertices.

Circuit → Path but the converse is false..right?

---

Which website you use to make this diagrams?

---

For these graphs Photo Editor by dev.macgyver.

Answer 2

Euler Path. Exactly two odd degree vertices must be present.

 

Euler Circuit. All vertices must be even degree.

 

Hence these are contradictory. And hence the Euler circuit and Euler path cannot exist together.

 

Sidenote: this is not true in hamiltonian world. Hamiltonian cycle -> Hamiltonian path.

Comments

Exactly two odd degree vertices must be present.

This the condition when there will be only euler path but no euler circuit.