Results 1 to 3 of 3

Math Help - Prove a graph doesn't exists

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    Prove a graph doesn't exists

    Hi,

    I have to prove that a 3-connected graph with 7 edges doesn't exists. I guess I should prove this statement by contradiction, but I don't know how to begin. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    To prove this is suffices to show that with 7 edges, there must always be a node with degree 2, or less.

    The strategy to show this is as follows. First, consider a fully connected graph of 5 nodes. (The reason we consider 5 not 4 is because fully connected graph with 4 nodes has 6 edges.) There are \binom{5}{2}=10 edges in this graph. We can construct *any* graph with 5 nodes and 7 edges by removing 3 edges from this graph.

    Consider removing the 3 edges (u,v),(w,x),(y,z). I claim that then at least two of u,v,w,x,y,z are equal. To see this note we have 5 vertices, and 6 of u,v,w,x,y,z. Thus one of these must be the same as at least one other by the pigeon hole principle. In the fully connected graph, each node has degree exactly 4. Since there is one repeated node in (u,v),(w,x),(y,z) (lets say u without loss of generality) then it must be that degree of u is 4 - 2 = 2.

    Now consider the general case. Suppose we have N vertices and 7 edges. There are \binom{N}{2} edges in the fully connected graph, and we can construct any graph with N edges and 7 edges by deleting \binom{N}{2}-7 edges. Now by the same pigeon hole argument as above, there is a node that drops by
    \left \lceil \frac{2(\binom{N}{2}-7)}{N} \right \rceil degree. Since each node has N-1 degree is suffices to show that

    N -1 - \left \lceil \frac{2(\binom{N}{2}-7)}{N} \right \rceil \le 2

    You can actually show that for N \ge 7 this is always true, since

     - \left \lceil \frac{2(\binom{N}{2}-7)}{N} \right \rceil \le -\frac{2(\binom{N}{2}-7)}{N}

    and for N \ge 7 it is easy to show that

    N - 1 - \frac{2(\binom{N}{2}-7)}{N}  \le 2.

    This means that the only case that remains for you to verify is with 6 nodes and 7 edges. Can you do that one yourself?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    Posts
    95
    Whats nice here is that you can extend this argument to any number of edges E, and connectivity K. That is, if you have the numbers



    N - number of nodes
    E - number of edges
    K - connectivity

    then if
    N - \left \lceil \frac{2(\binom{N}{2}-E)}{N} \right \rceil \le K<br />

    then there can not exist a graph with N nodes, E edges and K connectivity.

    Perhaps one can make this argument stronger and prove the converse? Hmm...

    Edit:
    Actually with I thought about it a little and I think its an if and only if. I'd need to prove it but I think the statement

    There exists a graph with N nodes E edges and K connectivity   \iff  N - \left \lceil \frac{2(\binom{N}{2}-E)}{N} \right \rceil > K

    is true. I showed the ==> direction above, and for the other way <== use the same argument as above to construct the graph with N nodes, E edges and K connectivity by taking the fully connected graph and deleting the edges such that no nodes degree drops below K, if the RHS is true then this should always be possible.

    edit:

    nevermind the converse is probably not true. ignore my thoughts on the converse, all I can guarantee is that the minimum degree >= K which is not enough to show K connectivity.
    Last edited by gmatt; May 4th 2010 at 04:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to prove such a sequence exists
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 6th 2011, 09:49 AM
  2. Prove that exists m among ai whose sum is at least m
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 11th 2011, 07:11 PM
  3. Prove that limit doesn't exist
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 8th 2010, 07:50 PM
  4. Replies: 16
    Last Post: November 15th 2009, 05:18 PM
  5. Replies: 0
    Last Post: April 21st 2009, 10:37 AM

Search Tags


/mathhelpforum @mathhelpforum