# Graph theory: proof

• Oct 28th 2009, 05:49 PM
zhupolongjoe
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....
• Oct 29th 2009, 03:49 AM
Plato
Quote:

Originally Posted by zhupolongjoe
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.
• Oct 29th 2009, 06:14 AM
zhupolongjoe
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.
• Oct 29th 2009, 09:20 AM
Swlabr
Quote:

Originally Posted by zhupolongjoe
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)$?
• Oct 29th 2009, 09:25 AM
Swlabr
Quote:

Originally Posted by zhupolongjoe
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$...
• Oct 29th 2009, 11:16 AM
zhupolongjoe
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.
• Oct 29th 2009, 11:58 AM
Swlabr
Quote:

Originally Posted by zhupolongjoe
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.
• Oct 29th 2009, 01:00 PM
zhupolongjoe
My apologies...you are correct there, I was misquoted the theorem...the inequality is the other way about.