3
$\begingroup$

I've always seen cycles in graphs described as containing three or more vertices. I had a question posed to me today that I now pose to you: Is it valid to consider a pair of vertices connected by a single edge in an undirected graph to be a cycle?

More concretely, given the following undirected graph:

a---b
 \ /
  c
  |
  d

Obviously, (c, b, a, c) is a cycle. Is (c, d, c)? Why or why not?

$\endgroup$
  • 4
    $\begingroup$ The edges in a cycle must be distinct, whatever its length. $cabac $ isn't a cycle either. $\endgroup$ – MJD Sep 2 '14 at 1:21
  • $\begingroup$ Oh, of course. Thank you! $\endgroup$ – asciiphil Sep 2 '14 at 11:11
-1
$\begingroup$

once this doubt occurred to me. It seams trivial, but when I am on doubt I always look for strong definitions, so this is what I found.

I will cite the definition of cycle in the book of Diestel, Graph Theory [http://www.flooved.com/reader/3447?no-redirect#16]

Page 8: "If $P=x_0 ... x_{k-1}$ is a path and $k \geq 3$, then the graph $C:=P+x_{k-1}x_0$ is called a cycle."

Thus $cdc$ is not a cycle because $cd$ is not a path with more than two vertices.

But what about $cdcdc$? It would be a path if $cdcd$ would. However, according Diestel definition of path (page 6) all vertices of a path are different.

$\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.