Graph Theory 3: Paths, Cycles, Degrees

Posted on December 30, 2013 by Brandon Coya

History is important, any history major will tell you that. Graph Theory was created by the famous mathematician Euler when he attempted to solve a problem involving some bridges. He wanted to know if someone could start somewhere in a town, walk across every bridge exactly once, and return to the start. To do this problem he used the notion of paths, cycles, and degrees.

First, two vertices are said to be adjacent if there is an edge connecting them. A path from one vertex to another vertex is a list of the labels in an order which specifies which edges to go along. Obviously to go from one vertex to another, they have to be adjacent. For example, if we have some 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.5,1.5){\line(1,1){.5}} \end{picture}

then a path from A to E could be written as ACDE. Another path would be ABE, and yet another would be ABCDE. The length of a path is the number of edges that it has. So the length of ACDE would be 3. With the idea of length we can ask what the shortest path between two points is, and how do we find it in general for any graph? This actually takes a lot more work to solve, so moving on.

A closed path is a path that starts and ends at the same place, so in the example above, DBACBED would be a closed path starting and ending at D. An open path starts and ends at different vertices.
A cycle is a closed path without any repetitions (other than the starting point). For example ABCA is a cycle of length 3, while DBACBED is not a cycle since it goes through B twice.

The last simple concept for today will be the degree of a vertex. The degree of a vertex is the number of edges that touch the vertex. In the above example the degree of A would be 2, while the degree of B would be 4. Math people use the notation d(A) = 2, d(B)=4.
When the degree is an odd number, we call the vertex an odd vertex, and similarly an even vertex is a vertex with even degree.

We used this concept last time without specifically mentioning it by name to get the number of edges in a complete graph. In a complete graph with N vertices, every vertex will have degree N-1.

An Euler path is a path that goes through every edge exactly once. We can have closed or open Euler paths. The degree of a vertex is the important concept to use when finding out when an Euler path exists. For example the below graph

\setlength{\unitlength}{7cm} \begin{picture}(2,5) \put(0,.1){A} \put(0,.9){B} \put(1.1,1){C} \put(1.1,0){D} \put(1.6,.5){E} \put(0,0){\circle*{1}} \put(0,0){\line(1,1){1}} \put(0,0){\line(0,1){1}} \put(0,1){\circle*{1}} \put(1,1){\circle*{1}} \put(1,0){\circle*{1}} \put(1,0){\line(-1,1){1}} \put(1.5,.5){\circle*{1}} \qbezier(0,0)(.5,.5)(1.5,.5) \qbezier(0,1)(.5,.5)(1.5,.5) \put(1,1){\line(1,-1){.5}} \end{picture}
has no Euler paths at any vertices. However we can find an open Euler path in the next graph starting at D and ending at C:
\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}} \put(1.5,1.95){1} \put(1.25,1.75){2} \put(1.25,1.25){3} \put(1.5,1.05){4} \put(2.05,1.5){5} \put(1.75,1.75){6} \put(1.75,1.25){7} \end{picture}
I’ve marked the path by numerical order in the picture, but it would be written out as:
\text{DEBACDBC}

The reasoning that this graph has an Euler path but the other graph doesn’t is subtle and needs a few more tools first. One such tool is the following.

The Degree Theorem: In ANY graph the sum of the degrees of every vertex is equal to twice the number of edges. We did something similar for complete graphs, but this is for any graph and the reasoning is exactly the same.

Taking all the vertices and adding up all their degrees gives you a total number of edges, but again each edge is counted twice, once for each vertex that it touches, so this sum is equal to twice the number of edges. In fancy math notation we can write it like this:

2N = \sum\limits_{i=1}^{k} d(v_i)
where N is the number of edges, and v_1,\ldots , v_k are the k vertices of the graph where k is some finite number, and d(v_i) is the degree of the i’th vertex.

This theorem is the key to finding when Euler paths exist and I will use it next time to do that.

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

Leave a comment