Graph Theory #self doubt

Question

Can both euler path and euler circuit exist in same graph.

Can both Hamiltonian path and Hamiltonian circuit exist in same graph.

Answer 1

Euler path and Euler circuit

No, a graph cannot contain Euler path and Euler circuit both.

Because for Euler path the graph must have exactly two vertices having odd degree but for Euler circuit all the vertices in that graph must have even degree.

Hamiltonian Path and Hamiltonian circuit

Yes, a graph can have both hamiltonian path and circuit.

Imagine a triangle ABC.

Then the path ABC is a hamiltonian path and the circuit ABCA is a hamiltonian circuit.

Comments

@kushagra , please check... https://en.wikipedia.org/wiki/Eulerian_path

http://discretetext.oscarlevin.com/dmoi/sec_paths.html

---

Ankit all your links are about eulerian trails . Here I am talking about eulerian path.

There is a difference between eulerian trail and eulerian path.

In a trail vertex can repeat but in a path vertex can't repeat.

---

@kushagra , but according to wikipedia , both are same..

Answer 2

both option are true.

• if a graph have euler circuit then it must have euler path . but converse not true.

• if a graph of all vertex are even degree then euler circuit must exist . and euler path also

• if a graph have 2 odd degree vertex then there exist a euler path but not euler circuit.

• Hamiltonian path and Hamiltonian circuit exist in same graph.

Comments

A path is a trail in which all vertices (except possibly the first and last) are distinct.

 

---

Can u show me any place or link where in  the definition of path the line (except possibly the first and the last ) is written.

---

Wikipedia + made easy note book