08_Euler and hamiltonian.pptx

euler and hamiltonian graphs

1. Euler and Hamiltonian Graphs Presented by:- Guided by: dr.ashok mishra Discrete mathematics PROJECT:-8 Rajnikant pandey (220101120115)

2. Euler graph :- A graph that contain an Euler circuit is called Euler graph. Euler path A path in a graph is called an Euler path if it contain every edge exactly once. Euler circuit A Circuit in a graph is called an Euler circuit if it contain every edge exactly once. Except first and last vertex.

3. Properties :- An undirected graph G is eulerian iff every vertex of G has even degree. An undirected connected graph G posses an Euler path iff it has either zero (no) or exactly two vertices of odd degree. Two vertices or odd degree are the end point or every Euler path.

4. Hamiltonian graph :- A graph that contain an Hamiltonian circuit is called Hamiltonian graph. Hamiltonian path A path in a graph is called an Euler path if it contain every edge exactly once. Hamiltonian circuit A Circuit in a graph is called an Hamiltonian circuit if it contain every vertices exactly once. Except first and last vertex.

5. Properties :- The complete bipartite graph Km,n is Hamiltonian iff m=n and n > 1. It is a simple graph G with ‘n’ vertices (n ≥ 3 ) , each vertices has degree atleast n/2 (if degree(v) ≥ n/2 ) where, V is a vertex of G. G is Hamiltonian. A complete simple graph Kn (n ≥ 3) is Hamiltonian.