Euler and Hamilton(circuit + path)

Characteristic of Euler circuit.

-A connected multigraph with at least two vertices has an Euler circuit if and only if each of the vertices has even degree.

-An Euler circuit is a connected graph such that starting at a vertex A, one can traverse along every edge of the graph once to each of the other vertices and return to vertex A.

-An Euler circuit exists if and only if every vertex of the graph has an even degree.

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

In an Euler circuit you can only pass through the edges only once.

Characteristic of Euler path.

-A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

An Euler path in a graph is a path which traverses each edge of the graph exactly once.

-For loopless graphs without isolated vertices, the existence of an Euler path implies the connectedness of the graph, since traversing every edge of such a graph requires visiting each vertex at least once.

-An Euler path exists if and only if it has exactly two vertices of odd degree.

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

In an Euler path you can only pass through the edges only once.

Characteristic of Hamilton circuit.

-A Hamiltonian path passes through each vertex (note not each edge), exactly once, and ends at the initial vertex then it is a Hamilton cycle.

If a simple graph with n vertices with n > = 3 such that the degree of every vertex in the graph is at least n/2, then it is a Hamilton graph.

-If a simple graph with n vertices with n > =3 such that deg (u) + deg (v) > = n for every pair of nonadjacent vertices u and v in the graph, then it is a Hamilton graph.

In a Hamiltonian circuit you may not pass though all edges.

Characteristic of Hamilton path.

A Hamiltonian circuit passes through each vertex (note not each edge), exactly once.

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

note :
1.if graph has a hamilton circuit, it automatically has a hamilton path

2.if graph has a euler circuit it cannot have euler path and vice versa

Graph

Description