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:
Cycle steps
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.

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ What do you mean by "add as many cycles as possible to the original 10-cycle" if I seek maximum components, should I continue to build on the same component? $\endgroup$ – Majilik Oct 13 '14 at 19:10
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 13 '14 at 19:11
  • $\begingroup$ Ah, thank you for clarifying this. I'm very grateful. $\endgroup$ – Majilik Oct 13 '14 at 19:19
  • $\begingroup$ @Majilik: You’re welcome. $\endgroup$ – Brian M. Scott Oct 13 '14 at 19:20

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.