# Thread: Show that if δ+Δ >= n-1, G is connected

1. ## Show that if δ+Δ >= n-1, G is connected

I think I'm almost there but I'm messing up on some step or two...

Suppose G is not connected, therefore G has two or more components such that C1 + C2 + C3+ ... + CM = n

Let Δ belong to C1, therefore C1 has size Δ+1.

C1 + C2 <= n
Δ+1 + C2 <= n
C2 <= n-Δ-1

Δ+1+n-Δ-1 <= n
Δ+1+(n-Δ-2) <= n-1
Δ+1+δ <= n-1
Δ+δ <= n-2
Δ+δ < n-1

Therefore if δ+Δ >= n-1, G is connected

Any tips, I think this proof looks a little weak and I'm pretty sure I'm messing up on the δ. For a disconnected graph I'm pretty sure that δ=n-Δ-#of components, but I'm not sure if I'm allowed to just put that in.

Thanks guys

2. dunno why i post here, never get any help anyway

3. ## Have to properly introduce new concepts and variables

Hi,

I can guess from your description that the subject is graphs, but it's hard to understand anything else. If you want that people who don't know anything about this particular problem understand it (and then help), you have to carefully describe every object that you use.

So G is probably a graph, but what are C1, etc? Later you say "Let Delta belong to C1." Does this make C1 a set? How do you add sets then? Is this set union? What is Delta and n? Without this knowledge the description is incomprehensible.

Evgeny

4. Originally Posted by glover_m
dunno why i post here, never get any help anyway