Definition talk:Cycle (Graph Theory)

Ok, I've been wondering this for a long time: say you have a graph consisting of two vertices and one edge connecting them. If you start at one vertex, cross the edge to the other, and then cross the edge back to the first, is it a cycle? --Cynic (talk) 01:28, 12 July 2009 (UTC)

See what you mean. We need to adjust the definitions as follows

A walk is as we've defined it.

A trail is a walk which doesn't repeat edges (as we've defined it).

A path needs to be defined as a trail whose vertices are distinct.

Then a cycle is a closed path.

As the walk you described isn't a trail (it repeats an edge), it's not a cycle.

Also need some weasel words to explain away the fact that, by this definition, a closed path doesn't strictly have "distinct vertices" because the first and last one are the same.

I'll get to it. --Matt Westwood 08:40, 12 July 2009 (UTC)