Search code examples
graphtheorygraph-theorycycle

Definition of cycle in undirected graph

I can't find a formal definition of cycle in an undirected graph. The CLRS only reports a definition of symple cycles that i can't manage to generalize for a generic cycle.

This is the CLRS definition: a symple cycle in a undirected graph is a path <v0,v1,..,vk> so that:

  1. k >= 3
  2. v0 = vk
  3. v1,..,vk are distincts

So i tried to remove the 3 condition to define a generic cycle but this can't work because we can have something like this: <a, b, c, b, a> that is obviously not a cycle.

Solution

  • I think you can generalize 3 as follows:

    1. Either v1,...,vk are distinct or they contain a simple cycle (a contiguous list of vertices satisfying 1,2,&3).