0
$\begingroup$

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.

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

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).

$\endgroup$
  • $\begingroup$ Thank you, the first part was part of the first section of the overall question, which now makes even more sense! $\endgroup$ – CalculatingKraken May 19 '16 at 19:40
0
$\begingroup$

A tree on 2015 vertices must have 2014 edges. But then we add precisely one more edge; if we make more than one cycle, then I claim there was actually a cycle in the graph to begin with. Indeed, the added edge must be part of both cycles, but then taking the two cycles together and removing the added edge, we obtain a cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.