Selected topics in finite mathematics/Eulerian cycles
An Eulerian Cycle is a cycle in a graph which contains every edge.
Objectives[edit | edit source]
Use every edge exactly once.
Details[edit | edit source]
A graph is connected if there is a path between any two vertices. If in a graph every vertex has an even number of edges incident upon it, the graph will have a Eulerian cycle.
A graph has an Eulerian Cycle if and only if all vertices have even numbers of edges. If a graph can't make an Eulerian Cycle, the process to make it a Eulerian Cycle is called Eulerizing.
A eulerian cycle is especially useful when trying to optimize paths and routes. For example, these cycles would be used when designing routes for trash collection, checking parking meters etc. Using a Eulerian cycle would allow one to save time by only walking down each street or pathway one time.
Examples[edit | edit source]
- The graph given in figure E1 is an Eulerian graph. Its edges are labelled with an Eulerian Cycle: A-B-C-D-E-F-G-H-I-J-K
Nonexamples[edit | edit source]
- In figure E1, A-B-C-I-H-K is not an Eulerian cycle because it misses an edge (several, in fact).
FAQ[edit | edit source]
Q: How do you know where to place new edges when you are trying to Eulerize an graph?
A: Add edges to all the vertices with odd degree, until every vertex has even degree. There are multiple ways to Eulerize a graph, some will be more efficient than others.
Homework[edit | edit source]
- Find an Eulerian cycle in the graph given in figure H1.