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

"for Euler path the graph must have exactly two vertices having odd degree"

I think , it should be atmost  instead of exactly. a graph has an euler path iff   atmost 2 vertices have odd degrees..since total no. of odd degree vertices are even..so it means for euler path ,either no vertex has odd degree or exactly 2 vertices have odd degree..

so , take a graph of single vertex...here, no vertex has odd degree..so it has euler path and here we have only one vertex which has zero degree and zero is an even number..so here every vertex has even degree also..so it is euler circuit also...

---

 ankitgupta.1729

you are right .

---

@Ankit download the pdf below

There in one of the slides you will get that if in a graph euler path exist then that graph must contain exactly two vertices having odd degree.

https://www.google.co.in/url?sa=t&source=web&rct=j&url=http://people.ku.edu/~jlmartin/courses/math105-F11/Lectures/chapter5-part2.pdf&ved=2ahUKEwjrjbmXqZ7bAhUM3Y8KHbrHCYUQFjABegQIBxAB&usg=AOvVaw0k-GR9qcJqcfJ9Uqvh3p9J

---

Theorem 2 must clear all doubts

---

@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