Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to prove that for any simple graph $G=(|E|,|V|, f)$

$|E| \leq (|V| - k + 1)(|V| - k) /2$

Where |E| - number of edges, |V| - number of vertices, and k - number of components.

Attempt at solution:

$$ν(G) = |E| - |V| + k(G) \geq 0$$

$$|E| \geq |V| - k$$

$$|E| + 1 \geq |V| - k + 1$$

$$(|E| + 1) (|V| -k) \geq (|V| - k + 1) (|V| -k)$$

$$(|E| + 1) (|V| -k) /2 \geq(|V| - k + 1) (|V| -k) /2$$

I know, that $(|V| -k) /2$ is always a positive number and if we remove it, we will lessen the left side. If we remove $+1$, we will lessen it even more. However, there is no guarantee, that we will lessen it enough to turn the sign the other way.

I really hope someone could help me.

share|cite|improve this question
If you have a given number of vertices and must connect them with the most edges you can while keeping them separated into $k$ components, it should be intuitively clear that the best strategy is to leave $k-1$ vertices as trivial components, and form a complete component from the rest of the vertices. Can you prove that moving a vertex from a larger (complete) component to a smaller will never increase the number of edges? – Henning Makholm Feb 28 '12 at 1:50
@HenningMakholm That is actually a fantastic insight, I haven't even noticed that the formula on the right is a number of edges of a complete component on (|V| - k +1) vertices. Now, I'll have to think about proving the second part you mentioned. – ivt Feb 28 '12 at 2:13
Would you like to type up your full solution and answer your own question? – Graphth Mar 14 '12 at 16:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.