Hamilton path and euler path

what is Hamilton path and Euler path?
History of Euler path and Hamilton path
Vertex(node) and edge
Hamilton path and Hamilton circuit
Euler path and Euler circuit
Degree of vertex and comparison of Euler and Hamilton path
Solving a problem

1. Hamilton P ath and Euler P ath

2. Things we are going to discuss History of Euler path and Hamilton path Vertex(node) and edge Hamilton path and Hamilton circuit Euler path and Euler circuit Degree of vertex and comparison of Euler and Hamilton path Solving a problem

3. History of Euler Path Euler path was first discussed by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736. The problem can be stated mathematically like this: a b c d

4. History of Hamilton Path Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the ICOSIAN game , now also known as Hamilton's puzzle , which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron

5. Vertex Vertex : Vertex typically means a corner or a point where lines meet. Vertex Not a Vertex

6. Edge: An edge is a line segment that joins two vertices Edge Edge

7. Hamiltonian Path and circuits In graph theory, an Hamilton path is a path which visits every vertex exactly once. Similarly, an Hamilton circuit is a circuit which starts and ends on the same vertex.

8. This has a Hamilton Path and a Hamilton circuit This has a Hamilton Path , but does not have a Hamilton circuit This has no Hamilton Path

9. Euler path and circuit In graph theory, an Euler path is a path which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.

10. This has an Euler Path and an Euler circuit This has an Euler Path , but does not have an Euler circuit This has no Hamilton Path

11. Degree of Vertex The degree of a vertex is the number of edges of the vertex.

12. Comparison of Euler and Hamilton circuits Property Euler Hamilton Repeated visits to a given node allowed? Repeated traversals of a given edge allowed? Omitted nodes allowed? Omitted edges allowed? YES NO NO NO NO NO NO YES

13. in the image, is it possible to construct a path ( a path starting and ending on the same vertex) which visits each edge exactly once? Seven Bridges Problem A B C D a b c d

14. Solve We know that , An E uler Circuit is possible if every vertex has even degree. An Euler path is possible but Euler Circuit is possible ,if exactly two vertices have odd degree. No Euler Path is possible if more than two vertices have odd degree. a b c d THERE IS NO EULERS PATH

15. THANK YOU !