1. ## 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....

2. 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 $\displaystyle \delta(G)~\&~\lambda(G)$ mean.

3. 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.

4. 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 $\displaystyle \delta (G) \leq \lambda(G)$ for every graph $\displaystyle G$." By definition $\displaystyle G$ should remain connected after we fewer than $\displaystyle \lambda(G)$ egdes. But then, just remove the $\displaystyle \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 $\displaystyle \delta(G) \geq \lambda(G)$?

5. 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 $\displaystyle \delta (G) \leq \lambda(G)$ for every graph $\displaystyle G$." But then by definition $\displaystyle G$ should remain connected after we fewer than $\displaystyle \lambda(G)$ egdes. But then, just remove the $\displaystyle \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 $\displaystyle \delta(G) \geq \lambda(G)$?

EDIT: For example, two triangles connected by a single line. Here, $\displaystyle 2=\delta(G) > \lambda(G)=1$...

6. 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.

7. 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.

8. My apologies...you are correct there, I was misquoted the theorem...the inequality is the other way about.