# Maximum possible of edges

Show that if G is a simple graph with n vertices and p connected components, the maximum possible number of edges in G is $\frac{1}{2}(n-p)(n-p+1)$

I know when G is simple, the max number of edges is $\frac{1}{2}n(n-1)$, but with the condition p connected components imposed, I have no idea how to proceed.

• – Moritz Oct 9 '16 at 16:40

Hint: The maximum number of edges arises when the graph consists of $p-1$ isolated vertices and a component with $n-p+1$ vertices all connected to each other.
• Do you mean that if I have $p-2$ isolated vertices and 2 components, one with $x$ vertices and one with $n-p+2-x$ vertices, having more edges? – mathshungry Oct 8 '16 at 17:27