What is the right definition of a cycle?
I've seen this in all introductory courses on graphs, but every time it bugs me : the definition of a cycle is usually wrong.
In the last course I have seen they define paths in the obvious way, adding edges inbetween vertices.
Then they say " a cycle is a non-trivial path whose first and last vertices are the same, but no other vertex is repeated" : but obviously this is wrong, since if there's an edge $\{a,b\}$, then the sequence $(a, \{a,b\}, b,\{a,b\}, a)$ is a non trivial path whose first and last vertices are the same, but no other vertex is repeated.
Now what's the proper definition of cycle ? The only way I can see this definition being correct is if "non-trivial" includes the example I gave. But then shouldn't the course mention it, as usually "trivial" means "with one element" or something along those lines ?
$\endgroup$ 31 Answer
$\begingroup$A cycle is either:
- a simple graph (= no double edges, no loops) with 1 component and all vertices having vertex degree 2
- a graph with 2 vertices and two edges between them
- a graph with 1 vertex and a loop
