# 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

## 1 Answer

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.

Prove this by showing that any graph not of this form can be modified to have more edges in total without changing the number of vertices and connected components.

• 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
• @mathshungry: In that case you can increase the number of edges by moving a vertex from the smaller of the components to the larger. – Henning Makholm Oct 9 '16 at 6:19