Hi Mathematics community,
Definition. Minimal cycles (those that contain no cycles as strict subsets) are called circuits. This also refers to Chordless cycle.
How many Chordless cycle exist in an undirected incomplete graph?
Can anyone give an upper bound on the number of Chordless cycles?
Is the number of Chordless cycles polynomial in terms of number of nodes?
I'm aware of this post which contains good information. Find cycles in graphs which do not contain other cycles
No, the number of chordless cycles can be exponential in the number of vertices of the graph.
Consider the $2k$-vertex graph whose vertices are divided into $k$ pairs which are arranged in a circle. Each vertex is connected to both vertices in each of the adjacent pairs. Here is a picture for $k=7$:
Here, there are at least $2^k = 2^{n/2}$ chordless cycles: any cycle of length $k$ formed by picking one vertex from each pair is chordless. (There are also other chordless cycles.)
An easy upper bound on the number of chordless cycles in a graph is $2^n$, since the vertex sets of the chordless cycles are all distinct. In fact, it's also true that one cycle's vertex set can't be a subset of another cycle's vertex set, so we can improve this slightly to $\binom{n}{n/2}$: the size of a maximum antichain in the subsets of $\{1,2,\dots,n\}$.