# How many cycles does a connected graph on 2015 vertices and exactly 2015 edges contain?

I understand that one possible answer is $1$ cycle because you can just have a path of $2015$ vertices ($e = n-1$, where $n$ is the number of vertices) and connect the last vertex with the first vertex thus having $2015$ edges and $1$ cycle.

But I don't think I can finish with that, is it wrong if I can see a graph with more than one cycle on $2015$ edges and $2015$ vertices? I see it as each cycle being a triangle, and being connected to the next triangle by one edge.

• How many edges does that graph you describe have? – Mariano Suárez-Álvarez May 19 '16 at 18:15
• You were right in the first place, your "triangles graph" has $3n$ vertices for $4n-1$ edges – Vincent May 19 '16 at 18:16

If there are no cycles, you have a tree, but a tree on $n$ vertices has $n-1$ edges. So there is at least one cycle.
Now if you take a cycle in your graph and remove one edge of that cycle, you have a connected graph with $2015$ vertices and $2014$ edges, and a connected graph with $n$ vertices and $n-1$ edges is a tree (prove by induction on $n$, using the fact that there must be at least one vertex of degree $1$). Adding an edge to a tree produces a graph with exactly one cycle (as Patrick Stevens noted).