[Math] Largest and least amount of connected components of graph with conditions

discrete mathematicsgraph theory

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.

Best Answer

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.