So, cyclicity doesnâ€™t really mean much for undirected graphs. Weâ€™ve made a decision in LightGraphs to allow cyclicity tests on undirected graphs (this merely checks to see whether ne(g) > 0), but the cycle enumeration algorithms (simple_cycles_hadwick_james and simple_cycles_iter) only work on directed graphs.

So, cyclicity doesnâ€™t really mean much for undirected graphs

Maybe it doesnâ€™t mean much to youâ€¦
Your response might be interpreted as being a little bit condescending.

There are real-world cases that can be represented as an undirected graph , where the question of the existence of cycles and n-cycles are of interest to the problem domain.

A better answer would be that any undirected graph can be seen as a directed graph where the existence of edge
from vertex i to vertex j , implies the existence of an edge from vertex j to I

Your response might be interpreted as being a little bit condescending.

That wasnâ€™t my intention. We actually had an extensive discussion about this on Gitter and in the LightGraphs issues where my original view was changed. The fact remains that an edge in an undirected graph from u to v can imply bidirectional connectivity, which creates a cycle. If you donâ€™t want that behavior in LightGraphs (which is the specific package to which the original question referred) then you must use a directed graph.

A better answer would be that any undirected graph can be seen as a directed graph where the existence of edge from vertex i to vertex j , implies the existence of an edge from vertex j to I

Except thatâ€™s potentially misleading in the context of LightGraphs, since we treat directed graphs as completely separate types from undirected graphs, with different backend storage. Your definition works in the abstract, but it does not reflect the design decisions we made in LightGraphs that might argue for a different approach to the problem.

If you have a meaningful definition of cyclicity that applies to undirected graphs, Iâ€™m all ears and would absolutely be willing to reopen the LightGraphs issue (above) in which we came to the conclusion that, in fact, cyclicity doesnâ€™t mean much in the context of undirected graphs.

How about a concept of cycles with no repeated edges? i.e. a sequence of edges where each shares a vertex with the previous and the next edge (and the last shares a vertex with the first). Also called a circuit in graph theory. Reference: https://en.wikipedia.org/wiki/Cycle_(graph_theory)

n-cycle for an undirected graph would be an ordered set of unique vertices of of size n : V1,V2,â€¦Vn
such that edge(Vi,Vi+1) exists for I=1:n-1 and edge(Vn,V1) also exists.

since it is an undirected and there is no way of telling a cycle from its circularly shifted version,
we consider only the equivalence class.

if the vertices has weight associated with them(for example index) , then a lexicographical order can be imposed and the minimum can be taken as a representative of the equivalence class.

what do you think?
I donâ€™t know if this is interesting or useful outside my problem domain , but it was a question I encountered.

(Thinking about this a bit more, if one restricts the problem to â€ścycles of exactly length Nâ€ť, we might be able to gain some efficiencies by not having to consider a substantial set of possible cycles. For example,

If we take the DAG of the graph, initialize â€śhead = rootâ€ť and then start at the head and follow the tree down N vertices across all branches to a target vertex â€śtargâ€ť, and then check to see whether thereâ€™s a (targ, head) edge in the original graph, we can determine whether thereâ€™s a cycle of length N that involves the head, and we get the set of vertices involved in that cycle (in cyclic order). We can then set â€śheadâ€ť iteratively to rootâ€™s children, doing the same thing, until there no more paths of length â€śNâ€ť exist in the DAG. There may be bugs in this approach, and there may be another commonly accepted way of doing this.)

I gather this implies that, for an undirected graph, Edge(i,j) is equivalent to Edge(j,i), at least as repetition is concerned? If so, I think this is equivalent to @TsurHermanâ€™s proposal below.

Actually, it is not equivalent, when considered carefully (an exercise for you). But this is a bit moot, as the original poster seems to have lost interest in explaining what he is after.

I confess to being distracted by JuliaCon right now, but if you want to humor me with the counterexample, I promise to be sufficiently embarrassed that it didnâ€™t occur to me at first read.

It seems this feature is till not implemented in LightGraphs. I found it both intuitive and useful to detect whether there is a simple cycle in an undirected graph.

Edit: A really useful observation by reading the StackOverflow is: when the graph is connected (happenly to be my usecase), it is a tree if there is no cycle in it. But it is really easy to check whether the connected graph is a tree: the number of edges of a tree is n-1 where n being the number of nodes of the graph.