**A. Notes**

A ** cycle** is a path, which is simple

**except that**the first and last vertex are the same (a path from a point back to itself).

ADCBA is a

*cycle*because only the first and last vertex are the same. ABCD is a*simple path*but not a*cycle*because the path does not go back to the starting point.CDABEA is a

*path,*but not a*simple path*because vertex A repeats.*cycle*because the starting and ending vertices are not the same.BCDAEB is a

*cycle*because only the starting and ending vertices are the same.Changing only the starting and ending vertex of a cycle will NOT create a new cycle, for example,

*ABCDA, BCDA, DABC and CDAB*are the same*cycle,*so they count as 1 cycle*.*

The **degree** of a vertex is the number of edges connected to that vertex.

So in the blue graph, vertex A has a degree of 3, vertex B has a degree of 3, vertex C has a degree of 5, and vertex D also has a degree of 3.

In 1735 Leonard Euler found that if a graph is traversable, the graph either has no vertex of odd degrees, or has only two vertices of odd degrees. And if a graph has no vertex of odd degrees, you can start at any vertex to traverse the graph; but if the graph has two vertices of odd degrees, you have to start at one odd-degree vertex and end at the other odd-degree vertex.

The path to traverse a graph is called a **Euler Path**.

The blue graph has 4 odd-degree vertices, so it is NOT traversable. The black graph above is traversable because it has two odd-degree vertices.

**B. HW**

Can you find three different cycles in the blue graph? Can you find more than three?

Can you find the Euler Path of the black graph above?

Can you find an Euler Path of the graph below?

yes, no

aebcd

abdcfe