Given a graph with $x$ edges and some number of vertices, what is the maximum number of cycles such a graph could possibly have?
Here is an example of what I mean:
Say you have 5 edges, then the maximum number of cycles would be 3 as in the following graph:
Vertices: {a,b,c,d} Edges: {(a,b),(b,c),(c,d),(d,a),(b,d)}
The 3 cycles are abd bcd and abcd. Also, I am thinking of a cycle as a subgraph so abd and dab are the same. I would like to know what the most possible number of cycles is for a graph with x edges.
Best Answer
The maximum number of cycles is infinity (if you allow cycles that repeat edges; and if you have at least 1 cycle).