**Theorem 1: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.**
**a**
**d**
**e**
**c**
**b**
**G**
**Illustration:**
**Here a,b,c,d,e are vertices.** **Each of the vertices have even degree.** **Hence the graph has an Euler circuit namely a,d,c,e,d,b,a. ** **Theorem 2: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.** **Theorem 2: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.** **(Note: Those two vertices are the end point of the path formed.)** **Illustration: **
**a**
**b**
**d**
**c**
**G**
**e**
**Here, a, b, c, d, e are vertices. ** **The vertices d, c and e have even degree and the vertices a and b have odd degree.** **Since the graph G has exactly two vertices with odd degree, it has an Euler path, namely, a, d, c, e, b, c, a, b ( a and b are end points ) but not an Euler circuit.**
**Share with your friends:** |