How to find connected components of a random graph?

Algorithm problem (graph and edges)?

• I need help to understand how to come up with a solution for this problem. Appreciate any help! A graph has n vertices and m edges. How many connected components that graph can have at most? How man connected components the graph can hav at least?

• Answer:

  I'll comeback later if I recall some math. However I would look through some combinatorics book. My first inkling is that there is some graph theorem that will give you exactly what you want, or it's an open question. I can tell you that the "at least" question is answerable if there are no restriction on vertex degrees. If there is some restriction on the degrees, a graph may not exist i.e. the degrees must sum to an even number.