Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$ Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$
I came up with this intuitively but was not able to prove it. The idea is that a graph with the maximum number of connected components would have individual nodes and 1 clique connected with at most one other node.
The derivation is to find an order n of a subset of V such that $\binom{n}{2}=E$, meaning that $n^2-n-2E=0$
Edit: We are given V number of vertices and E number of edges and solving for maximum number of connected components
 A: Hint: You may assume that each connected component is a complete graph. This only decreases your bound, hence it is still a maximum.
Edit: Observe that if $E^* \geq E$, then $\lceil \frac{ 1 + \sqrt{1+8E^*}}{2} \rceil \geq \lceil \frac{ 1 + \sqrt{1+8E}}{2} \rceil$. Hence, if we increase the number of edges and the bound still holds, then 

 we know that the bound is true in the initial case.

Hint: Apply the convexity of ${ n \choose 2 }$, to further increase the total number of edges, given that there are $k$ connected components.
Edit: Assume that you have connected components of size $n_1, n_2, \ldots n_k$. Then since they are a complete graph, there are $ E = {n_1 \choose 2} + { n_2 \choose 2} + \ldots {n_k \choose 2} $ edges. By convexity, we know that $E \geq k { \frac{V}{k} \choose 2} = E^* $. It remains to verify that

 $$ k \leq V+1 - \lceil \frac{ 1 + \sqrt{1+8E^*}}{2} \rceil $$

A: Assume there is a graph with the maximum number of connected components that has multiple components with more than one node. This graph can be reduced to having only one component with more than one node, without changing the number of edges or connected components (by taking every node with degree>0 and connecting it to the biggest connected component, and disconnecting it from its previous one). 
This implies that we're left with a single collective component that is atomic (That is, can't be separated into multiple connected components and retain the total number of edges). I claim that this single connected component must be a clique with at most one additional connected node. Proof sketch: let the pair $(n_1,E_1)$ denote a whole number solution to $x^2-x=2y$ such that $y\leq E$ is maximized. If $E-E_1\geq n_1$, then $(n_1+1, E_1+n_1)$ would also be a solution. Therefore, $E-E_1<n_1$. One additional node is enough to cover the remaining edges since there are fewer than $n_1$, proving that we can satisfy given edges $E$ with $n_1+1$ nodes. If $n>n_1+1$, then by having such a graph the remaining nodes are each connected components of their own, contradicting that the original component must be atomic. That basically proves my claim.
