0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.