[Oops.] A single edge is not a cycle

[nitramsivart]

Please verify that the error is present in the most recent revision before reporting.

Chapter number or note title: 5

Page number: 191

Error description: The definition of cycle allows a single edge uv to be a cycle with the walk u,v,u. The book states:

• A walk in an undirected graph G is a sequence of vertices, where each adjacent pair of vertices are adjacent in G
• A walk is closed if it starts and ends at the same vertex; a cycle is a closed walk that enters and leaves each vertex at most once

By these definitions, the walks uvu or just u would be a cycle.

Suggested fix (if any): Not sure what's cleanest. I know that CLRS defines a "simple cycle" as a closed walk with distinct edges and vertices (except the endpoint). Alternatively, you could say a cycle is a closed walk with at least 4 vertices.

[ijustlovemath]

There are no pairs in u, so perhaps the walk definition doesnt apply to that one.

[nitramsivart]

The walk definition should still apply, as "each adjacent pair of vertices are adjacent in G" is vacuously true when there are no pairs.

A single vertex is just a zero-length walk. This convention is used other places in the book, for example, in the definition of connected on the same page. We'd certainly say that a vertex is reachable from itself, and that a single vertex is a connected graph.