# Largest and least amount of connected components of graph with conditions

A graph G without loops and parallel edges has the following properties:$$|V|=30$$$$|E|=30$$ It also has a cycle of length 10. What is the largest and the least amount of connected components in the graph G?

What I've tried is to draw the cycle as steps through the same edge between two vertices like the image below:

The remaining vertices and edges are: $$|V_{remaining}| = 28$$$$|E_{remaining}|=29$$ These should then form the maximum amount of components together with the cycle as it's own component.
Am I doing this correct or is there another way to approach this problem? I'm stuck at this point.

• I would assume (but I might be wrong) that by cycle they mean a simple cycle. Otherwise, there would be no point in saying that it has a cycle of length 10. – Michelle Oct 13 '14 at 17:34

HINT: I don’t understand your picture: a cycle of length $10$ requires $10$ vertices and $10$ edges, so there are $20$ vertices and $20$ edges remaining.
• Find a way to attach the remaining $20$ vertices to the $10$-cycle using exactly $20$ edges, thereby producing a connected graph; this shows that the minimum possible number of components is $1$.
• Notice that in any cycle the number of edges is equal to the number of vertices. To maximize the number of components, add as many cycles as possible to the original $10$-cycle. You’ll want to make them as small as you can.
• @Majilik: If you want the largest possible number of components, you clearly should not continue to build on the same component. The new cycles should be disjoint from one another and from the original $10$-cycle. – Brian M. Scott Oct 13 '14 at 19:11