2
$\begingroup$

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

enter image description here

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 29, 2018 at 1:16
  • $\begingroup$ @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. $\endgroup$ Jan 29, 2018 at 1:27
  • $\begingroup$ Thanks a lot for your help @FabioSomenzi, post your solution and I will accept it because it really clarified things up. $\endgroup$ Jan 29, 2018 at 1:28

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for clarifying things up. Also, that was a nice tip at the end, I make sure to keep that in mind :) $\endgroup$ Jan 29, 2018 at 7:44
  • $\begingroup$ You're welcome :) $\endgroup$
    – ArsenBerk
    Jan 29, 2018 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.