5
$\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$
2
  • 6
    $\begingroup$ The edges in a cycle must be distinct, whatever its length. $cabac $ isn't a cycle either. $\endgroup$
    – MJD
    Sep 2, 2014 at 1:21
  • $\begingroup$ Oh, of course. Thank you! $\endgroup$
    – asciiphil
    Sep 2, 2014 at 11:11

0

You must log in to answer this question.

Browse other questions tagged .