1. ## Graph Theory Problem

Let G be an n-vertex simple graph, where n >= 2. Determine the maximum possible
number of edges in G under each of the following conditions.
(a) G has an independent set of size a.
(b) G has exactly k components.
(c) G is disconnected

Any ideas? Thanks

2. a) (n-a)(n-a-1)/2 + (n-a)a

Consider a clique of n-a vertices. Join each vertex of that clique with each of the "a" vertices of the independent set.

b) (n-k+1)(n-k)/2

Consider k-1 isolated vertices, and a clique of n-k+1 vertices.

c) (n-1)(n-2)/2

Consider the case when k=2.

3. Can you show how to get that? I'm lost when it comes to this subject...

4. a) Since you want to maximize the number of edges, if you need G to have an independent set I of size a, that should be the largest possible independent set as well, and there should not be any independent set of more than one vertex, that is disjoint from I. The vertices of I must not have any edge between them. So you can consider all the other edges possible. This means that there will be all possible edges between n-a other vertices, and all possible edges between each of these n-a vertices and vertices of I. the former evaluates to C(n-a,2) and the latter to (n-a)a.

b) Suppose you have k components. Whatever number of vertices each of them might have, to maximize the number of edges you will have to turn them into k disjoint cliques. Let the ith component c_i have a_i vertices. So the number of edges it has will be C(a_i,2) = a_i(a_i - 1)/2 .

Now, given any such G of n vertices having exactly k components, we will see how G' of n vertices with k-1 isolated vertices and the rest clumped into a huge clique has at least as many edges as G. To observe this, we will transform G into G', keeping the number of edges the same, or increasing it in each step involved.

Without the loss of generality, assume that a_1 >= .... >= a_i +..... >= a_k. Choose any c_i other than c_1. Take any vertex from this c_i, delete all its edges to other vertices of c_i and draw edges from it to all vertices of c_1. So the vertex loses a_i - 1 edges, gains a_1 - 1 edges and becomes a part of the component c_1. Since a_1 >= a_i, the vertex (and hence G ) gains at least as many edges it loses. Repeat this process until there is only one vertex left in c_i. Repeat this process with every other c_i (other than i =1 ) until all of them are isolated vertices. What you have now is G' and the proof is complete.

The number of vertices in the only non-trivial clique of G' is n-k+1. So the number of edges will be C(n-k+1,2) = (n-k+1)(n-k)/2

c) Follows from b).