1
$\begingroup$

My textbook provides a strange definition for cycles in undirected graphs, arguing that they must be at least $3$ in length (something like $<a, b, c, a>$), essentially meaning that, for instance, $<a, b, a>$ or $<a>$ are not cycles.

But that doesn't make sense to me, and I doubt whether my book is correct about this,considering its definition of cycles in the chapter on digraphs did not impose any such restriction. I couldn't find any information online about this.

Is this rule true? If so, why?

$\endgroup$
  • 1
    $\begingroup$ You need to check in your book the conditions that they are imposing the graphs to have. Depending on the book, sometimes graphs are assumed not to have loops $(a,a)$, and perhaps sometimes they could be assuming that for any pair of vertices there is at most one edge. $\endgroup$ – Hellen Jul 26 '17 at 20:51
  • 1
    $\begingroup$ For example, in Wikipedia the edges are unordered pairs of vertices. Therefore $(a,b)$ and $(b,a)$ are the same edge. Assuming their graphs are simple. $\endgroup$ – Hellen Jul 26 '17 at 20:53
  • $\begingroup$ @Hellen, it seems that what you wrote almost constitutes an answer. In a case like that, you might want to provide a full answer instead of a comment. In any case, I expanded your thoughts (mixed with my point of view) into a community wiki answer. Please feel free to contribute (comment/add/remove/replace) as you see fit. :-) $\endgroup$ – Josse van Dobben de Bruyn Jul 29 '17 at 0:02
  • $\begingroup$ If you allow length $2$ and don't require the edges of a cycle to be distinct, you'll get degenerate cycles like $\left(a,b,a\right)$ whenever your graph has at least one edge. But this would prevent you from easily stating important facts such as "a tree is a graph with no cycles". That said, it is better to require the edges of a cycle to be distinct instead (because this requirement becomes necessary for multigraphs anyway), and to define trees as multigraphs (even though they never have parallel edges). $\endgroup$ – darij grinberg Jul 29 '17 at 0:36
1
$\begingroup$

Though I don't know which book you are using, I shall assume that all graphs are simple (otherwise we may refer to them as multigraphs).

The case of cycles of length $2$ comes down to the difference between cycles and closed walks. Cycles are usually assumed to be simple, that is, not use any vertex or edge more than once (except that it starts and ends in the same vertex). For instance, we would not consider $C_4$ to have a cycle of length $6$, even though it does have a closed walk of length $6$. Therefore we also do not consider something like $\langle a,b,a\rangle$ to be a cycle.

The case of the single-vertex cycle $\langle a\rangle$ is a bit trickier. Couldn't we say the begin and end point of this cycle are the same, with no edges in between them? (After all, a simple graph is not allowed to have loops.) Well, yes, that would make it a cycle of length $0$. This is a degenerate case: it does not suit any practical use, and it defies the usual properties of cycles that we know (for instance: "the number of vertices on a cycle is the same as the number of edges"). Furthermore, it complicates various definitions (such as: "a forest is a graph without cycles", or "the girth of $G$ is the length of the shortest cycle in $G$"). For this reason the trivial cycle is often excluded.

Maybe somebody has a more compelling reason why a trivial cycle should be excluded, but I see it mostly as a matter of convention. In any case, rest assured: the definitions you encountered are common. In graph theory (and mathematics in general), sometimes definitions are modified to exclude degenerate cases or to prevent strange corner cases from turning up further down the line.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.