Graph Theory 4: Existence of Euler Paths

Recall that an Euler path is a path that goes through every edge exactly once. We are going to start by trying to find when an open Euler path exists. In all of the following I am assuming that the graphs are connected. A path has to start somewhere, so lets look at two possibilities. The starting vertex can have either an even degree or an odd degree.
First the even case, an example is below of degree 4.
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(0,.1){A}  \put(0,0){\circle*{1}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(0,1){1}}  \qbezier(0,0)(.5,.5)(1.5,.5)  \qbezier(0,0)(.25,.75)(1.5,.5)  \end{picture}
If we start here, then we are going to have to also end here if we want to hit every edge exactly once. This is because we go “out” first, so eventually we end by going “in” regardless of what happens between. However, we want an open Euler path, which means it cannot start and end at the same place, so we know that to get an open Euler path we cannot start at an even vertex.

Next we can see what happens if the path starts at an odd vertex.
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(0,.1){A}  \put(0,0){\circle*{1}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(0,1){1}}  \qbezier(0,0)(.5,.5)(1.5,.5)  \end{picture}

This works for now! We can start here and the last time we touch this vertex we will be going “out” from it, so we definitely won’t start and end at the same place.

What about if we go “in” to this vertex? Well then we have to go out and back in once more and that would end it since we have no more ways to leave the vertex. This is true for any odd vertex. What does this tell us? It means that an odd vertex has to be either the beginning or the ending of an open Euler path. Since if we start at an odd vertex, we have to eventually leave it, but if we don’t start at an odd vertex, we have to eventually end the path at it.

If we have a third odd vertex then we can no longer make an Euler path because the first two odd vertices are already taking up the beginning and ending positions of the path.

I also never checked what happens when you start by going “in” to an even vertex. If we start by going in, then we have to end by going out of it, which is what we want. We need some recap at this point. To get an open Euler path we can only have two odd vertices, and one has to be the start and the other the end. Everything other vertex has to have even degree so that we can go into it and come back out to a different vertex. These are called necessary and sufficient conditions for an open Euler path to exist in a graph.

Consider the following graph as a good example:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1,1.1){A}  \put(2,1){\circle*{1}}  \put(2.1,1){C}  \put(1.5,1.5){\circle*{1}}  \put(1.4,1.5){B}  \put(1,1){\line(1,1){.5}}  \put(1,1){\line(1,0){1}}  \put(2,2){\circle*{1}}  \put(2.1,2){D}  \put(2,2){\line(0,-1){1}}  \put(1,2){\circle*{1}}  \put(1.1,2){E}  \put(1,2){\line(1,0){1}}  \put(1,2){\line(1,-1){.5}}  \put(1.5,1.5){\line(1,-1){.5}}  \put(1.5,1.5){\line(1,1){.5}}  \end{picture}

Only D and C have odd degree, so to make an Euler path we have to start at either vertex and end at the other one. Notice what happens as you start to trace along a path in the graph. The even vertices are all allowing you to go into them and then come back out to a different vertex, while the odd ones are forced to be the beginning or ending points. This concludes when we can draw an open Euler path.

So how about a closed Euler path. Remember, this is a path which starts and ends at the same place, and goes through every edge exactly once.

We’ve already talked about starting at an odd vertex and the conclusion was that the last edge will be going “out” from it, so we cannot start and end an Euler path at an odd vertex.

So we must have to start at an even vertex instead. Can there be any other odd vertices in the graph though? The answer is no. If we have an odd vertex somewhere in the graph then we unfortunately have to end at it, as I stated earlier, but we want to start and end at the same place. This means that to have a closed Euler path that all the vertices must be of even degree.
For example:

\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1,1.1){A}  \put(2,1){\circle*{1}}  \put(2.1,1){C}  \put(1.5,1.5){\circle*{1}}  \put(1.4,1.5){B}  \put(1,1){\line(1,1){.5}}  \put(1,1){\line(1,0){1}}  \put(2,2){\circle*{1}}  \put(2.1,2){D}  \put(1,2){\circle*{1}}  \put(1.1,2){E}  \put(1,2){\line(1,0){1}}  \put(1,2){\line(1,-1){.5}}  \put(1.5,1.5){\line(1,-1){.5}}  \put(1.5,1.5){\line(1,1){.5}}  \end{picture}

Every vertex has even degree in this graph and you can form a closed Euler path at any vertex. Every vertex being even is sufficient to have a closed Euler path because of the previous discussion. Starting at an even vertex means that you must end at the same one in order to hit every edge once, while going “in” to an even vertex means that you must leave it eventually. This means that I can leave all of the other vertices and that I can end at the one I started with so long as they all have even degree.

I did glance past one small issue while discussing the open Euler paths. Do you see what it is? I stated that I cannot have more than two odd vertices, but can you see why I need exactly two, and not just one? One reason comes from the formula that I derived yesterday, i.e.

2N = \sum\limits_{i=1}^{k} d(v_i)

This says that the sum of the degrees must be 2(number of edges). Well it doesn’t matter how many edges you have, 2 multiplied by anything is going to be an even number. Which means that the sum of the degrees must be an even number. If we have only one vertex of odd degree, and the rest are all even then the sum looks like

\text{odd + even + even + even... + even} which forms an odd number no matter what. But I just showed that this sum has to form an even number, therefore this degree sum is impossible meaning that we cannot have just one odd vertex. (In fact we can never have an odd number of odd vertices by the same reasoning)

Try to find either an open or closed Euler path in this graph:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1,1.1){A}  \put(2,1){\circle*{1}}  \put(2.1,1){C}  \put(1.5,1.5){\circle*{1}}  \put(1.4,1.5){B}  \put(1,1){\line(1,1){.5}}  \put(1,1){\line(1,0){1}}  \put(2,2){\circle*{1}}  \put(2.1,2){D}  \put(2,2){\line(0,-1){1}}  \put(1,2){\circle*{1}}  \put(1.1,2){E}  \put(1,2){\line(1,0){1}}  \put(1,2){\line(1,-1){.5}}  \put(1.5,1.5){\line(1,-1){.5}}  \put(1,1){\line(0,1){1}}  \put(1.5,1.5){\line(1,1){.5}}  \end{picture}

You will find that it is impossible. You get stuck finishing at an odd vertex before you’ve used up all the paths.

Advertisements
This entry was posted in Graph Theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s