Results 1 to 8 of 8

Math Help - Graph theory: proof

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Graph theory: proof

    Prove that if G is a graph of order n such that delta(G)>=(n-1)/2, then lambda(G)=delta(G).

    Well, because delta(G)>=(n-1)/2, we know G is connected from a previous result. Also, this bound was proven to be sharp. We also know by a theorem that delta (G)<=lambda(G) for every graph G. So if we could just show that it is not the case that delta (G) < lambda(G), we would be done.
    This is where I am stumped. I am pretty sure it involves the inequality with delta(G), but I don't know what to do with it....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,786
    Thanks
    1683
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Prove that if G is a graph of order n such that delta(G)>=(n-1)/2, then lambda(G)=delta(G).
    Well, because delta(G)>=(n-1)/2, we know G is connected from a previous result. Also, this bound was proven to be sharp. We also know by a theorem that delta (G)<=lambda(G) for every graph G. So if we could just show that it is not the case that delta (G) < lambda(G), we would be done.
    This is where I am stumped. I am pretty sure it involves the inequality with delta(G), but I don't know what to do with it....
    You have not told us what \delta(G)~\&~\lambda(G) mean.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    I was taught that delta and lambda had universal meaning in graph theory. Delta(G) being the minimum degree in G and lambda meaning the edge-connectivity of G.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by zhupolongjoe View Post
    Prove that if G is a graph of order n such that delta(G)>=(n-1)/2, then lambda(G)=delta(G).

    Well, because delta(G)>=(n-1)/2, we know G is connected from a previous result. Also, this bound was proven to be sharp. We also know by a theorem that delta (G)<=lambda(G) for every graph G. So if we could just show that it is not the case that delta (G) < lambda(G), we would be done.
    This is where I am stumped. I am pretty sure it involves the inequality with delta(G), but I don't know what to do with it....
    Something isn't right here, but maybe it is just me. However, you said that "We also know by a theorem that \delta (G) \leq \lambda(G) for every graph G." By definition G should remain connected after we fewer than \lambda(G) egdes. But then, just remove the \delta(G) edges that are attached to the vertex of minimum degree to get a disconnected graph...so at best you have equality.

    Do you perhaps mean \delta(G) \geq \lambda(G)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by zhupolongjoe View Post
    Prove that if G is a graph of order n such that delta(G)>=(n-1)/2, then lambda(G)=delta(G).

    Well, because delta(G)>=(n-1)/2, we know G is connected from a previous result. Also, this bound was proven to be sharp. We also know by a theorem that delta (G)<=lambda(G) for every graph G. So if we could just show that it is not the case that delta (G) < lambda(G), we would be done.
    This is where I am stumped. I am pretty sure it involves the inequality with delta(G), but I don't know what to do with it....
    Something isn't right here, but maybe it is just me. However, you said that "We also know by a theorem that \delta (G) \leq \lambda(G) for every graph G." But then by definition G should remain connected after we fewer than \lambda(G) egdes. But then, just remove the \delta(G) edges that are attached to the vertex of minimum degree to get a disconnected graph...so at best you have equality.

    Do you perhaps mean \delta(G) \geq \lambda(G)?

    EDIT: For example, two triangles connected by a single line. Here, 2=\delta(G) > \lambda(G)=1...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    No, I meant the equality because what you wrote contradicts the theorem that has the inequality the opposite way around.

    For the two triangles with the line, n=6, and so (n-1)/2=5/2, but delta G=2, and so this is not a graph satisfying my condition.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by zhupolongjoe View Post
    No, I meant the equality because what you wrote contradicts the theorem that has the inequality the opposite way around.

    For the two triangles with the line, n=6, and so (n-1)/2=5/2, but delta G=2, and so this is not a graph satisfying my condition.
    No it doesn't satisfy the condition, but it contradicts the theorem you quoted.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    My apologies...you are correct there, I was misquoted the theorem...the inequality is the other way about.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2010, 11:00 PM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2010, 11:59 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 08:34 AM
  4. Graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 09:01 PM
  5. Graph Theory Proof please:-
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2008, 03:06 PM

Search Tags


/mathhelpforum @mathhelpforum