Difference between hamiltonian path and euler path

algorithm graph graph-theory hamiltonian-path euler-path
mousey picture mousey · Jul 16, 2010 · Viewed 101.4k times · Source

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Answer

Chris Diver picture Chris Diver · Jul 16, 2010

An Euler path is a path that passes through every edge exactly once. If it ends at the initial vertex then it is an Euler cycle.

A Hamiltonian path is a path that passes through every vertex exactly once (NOT every edge). If it ends at the initial vertex then it is a Hamiltonian cycle.

In an Euler path you might pass through a vertex more than once.

In a Hamiltonian path you may not pass through all edges.

Related questions

Cycles in an Undirected Graph

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Read More
How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' …

Read More
Names of Graph Traversal Algorithms

What I'm looking for is a comprehensive list of graph traversal algorithms, with brief descriptions of their purpose, as a jump off point for researching them. So far I'm aware of: Dijkstra's - single-source shortest path Kruskal's - finds a …

Read More