Graph Theory: Euler Trail and Euler Graph

Question

- 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.

Answer 1

They are nice questions actually, not only for understanding the general concept but also they prepare you to understand the proof of Euler Path Theorem. I will explain why in the end.

For your first question, yes, you are right. It is because before removing blue edge, every vertex had even degree. Since an edge is between two vertices, when we remove an edge, as long as we don't make the graph disconnected, we will get an Euler trail since there will be two vertices with odd degree.

For your second question, again, you are right. Because we can have an Euler trail such that our start vertex and terminal vertex are the same. This becomes Euler cycle and since every vertex has even degree, by the definition you have given, it is also an Euler graph.

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.