Models of Computation - Mathematics 450 - Fall 2006

3(b): A graph is bipartite iff it is 2-colorable.

3(e): An Euler path (respectively, circuit) is a path (respectively, circuit) that traverses every edge exactly once.A path is, loosely speaking, a sequence of consecutively adjacent edges; more precisely, it is a sequence of edges e₁ ,e₂ ,..., e_n, such that for each i, one vertex of e_i is in e_i-1 and the other vertex is in e_i+1. A circuit is a closed path, i.e., a path that starts and ends at the same vertex.