Lecture six covers the basics of Euler cycles and Hamiltonian circuits and their variants. The fundamental theorem about Euler cycles, due to Euler (1732), is considered the first theorem of graph theory, and asserts that a graph has an Euler cycle if it is connected (up to isolated vertices), and if every vertex has even degree. Proof, and its variants, are straightforward, and are in the Tucker text.

The existence or non-existence of an Euler cycle is easy to determine: just look at the degrees of the vertices.

A Hamiltonian circuit is a circuit that visits every vertex exactly once, then returns to the starting vertex.

-- RobbieMoll - 26 Sep 2006

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2006-09-26 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback