Graph theory: proof

Printable View

October 28th 2009, 04: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....
October 29th 2009, 02: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.
October 29th 2009, 05: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.
October 29th 2009, 08: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)$ ?
October 29th 2009, 08: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$ ...
October 29th 2009, 10: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.
October 29th 2009, 10: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.
October 29th 2009, 12:00 PM
zhupolongjoe

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