# Graph Theory: Euler Trail and Euler Graph

- Background Information:

I am studying graph theory in discrete mathematics. As I was reading my notes, I came across few definitions. I think I have noticed a pattern, but I need to confirm it with someone, thanks.

• Definition of Euler Graph:

Let G = (V, E), be a connected undirected graph (or multigraph) with no isolated vertices. Then G is Eulerian if and only if every vertex of G has an even degree.

• Definition of Euler Trail:

Let G = (V, E), be a conned undirected graph (or multigraph) with no isolated vertices. Then G contains a Euler trail if and only if exactly two vertices of G are of odd degree.

- My Example:

• Look at the image above, consider the vertices with black edges (imagine blue edge does not exist) to be undirected graph G.

- Questions & Patterns:

• Without the blue edge (a,b), we have a Euler trail, am I right? Explain why.

• With the blue edge (a,b), we have a Euler graph which is also a Euler cycle in this case, am I right? Explain why.

• A Eulerian graph is a (connected, not conned) graph that contains a Eulerian cycle, that is, a cycle that visits each edge once. The definition you have is equivalent. If you remove an edge from a Eulerian graph, two things happen: (1) two vertices now have odd degree. (2) you can still visit all the edges once, but you cannot close the cycle. The resulting path is called Eulerian trail. Jan 29, 2018 at 1:16
• @FabioSomenzi, yes you are right, the Eulerian graph is connected, I made a typo and I fixed it. I mixed up few definitions, but now I got it. Thus, Without the blue edge (a,b), we can get a Euler trail, and with the blue edge, we can have a Euler graph which is a Eulerian cycle. Jan 29, 2018 at 1:27
• Thanks a lot for your help @FabioSomenzi, post your solution and I will accept it because it really clarified things up. Jan 29, 2018 at 1:28

ABOUT EULER PATH THEOREM: Of course what I'm about to say is a matter of style but while teaching Graph Theory some teachers first give the proof of Euler Cycle part of Euler Path Theorem, then when they give the Euler Trail part of the theorem, they simply say "say only two vertices $s$ (stands for start) and $t$ (stands for terminal) have odd degree. Let us connect these vertices with an edge. Since the new graph has an Euler cycle (s/he has proved it already), we can have a circuit $s \rightarrow ... \rightarrow t \rightarrow s$. So removing the edge $\{st\}$ gives us the Euler trail". Now that you asked these questions, I believe you will better understand the proof of Euler Path Theorem if you haven't seen it yet.