Lecture 14 - Notes

February 29, 2016

Eulerian Cycle

contains every edge once

• the origins of graph theory, bridges of Konigsberg

• see wikipedia article

Hamilton Cycle

Contains every vertex once

Some Theorems

• A undirected graph has a Eulerian cycle iff every vertex has even degree
• A directed graph has a Eulerian Path iff exactly 2 vertices have odd degrees