**Identifying Euler circuits and Euler paths:** **Identifying Euler circuits and Euler paths:** **Undirected graphs:** **The graph G 1 has an Euler circuit, for example a,e,c,d,e,b,a .** **The graph G2 has neither an Euler circuit nor an Euler path.** **The graph G3 doesn’t have an Euler circuit but it has an Euler path, namely, a,d,c,e,b,c,a,b . **
**a**
**b**
**d**
**c**
**G1**
**a**
**d**
**e**
**c**
**b**
**G2**
**a**
**b**
**d**
**c**
**G3**
**e**
**Directed graphs:** **Directed graphs:** **The graph H1 has an Euler path, namely d,a,b,d,c,b .** **The graph H2 has an Euler circuit, namely, a,g,c,b,g,e,d,f,a.**
**d**
**c**
**b**
**a**
**H1**
**a**
**b**
**c**
**d**
**e**
**f**
**g**
**H2**
**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.**
**Share with your friends:** |