Results 1 to 4 of 4

Math Help - Graph Theory Problem

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Can you show how to get that? I'm lost when it comes to this subject...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 20th 2010, 03:44 AM
  3. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  4. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 10:08 PM
  5. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 26th 2007, 11:56 AM

Search Tags


/mathhelpforum @mathhelpforum