common neighbors (graph theory)

[hero]

Let G be aa simple graph with n vertices

a) Let x & y be nonadjacent vertices of degree at least (n+k-2)/2. Prove that x & y have at least k common neigbors.

b) Prove that if every vertex has degree at least [n/2], then G is connected. show that this bound is best possible whenever n>=2 by exhibiting a disconnected n-vertex graph where every vertex has at least [n/2]-1 neighbors.

Note: [] represents the greatest value function.


Please help. thank you very much.

[pka]

I frankly have no clear idea how to proceed with part a. I suspect that it is some sort of induction argument. Usually those sorts of problems have a clever trick, which makes it easy if you are lucky to see the trick.

For part b. For any graph with n vertices can have at most \frac{{\left( {n - 1} \right)\left( {n - 2} \right)}}{2} edges if it is disconnected. Using this relationship \frac{{2\left| E \right|}}{n} \ge \min \left( {\mbox{deg}v_k } \right)\quad \Rightarrow \quad \left| E \right| \ge \frac{n}{2}\left\lfloor {\frac{n}{2}} \right\rfloor you can finish it off.

[hellerj]

This might be a wee bit late to help you:smile:. But I had the same problem for homework this week and this is how i did it:

Let Vx and Vy be the sets of the neighbors of x and y respectively. Let C be the number of common neighbors between x and y. Let R be the number of vertices which are not x, y, or neighbors of x,y. We know that:

d(x)=|Vx|

d(y)=|Vy|

n=2+|Vx U Vy|+R => |Vx U Vy|=n-2-R

C=|Vx ∩ Vy|

|Vx U Vy|=|Vx|+|Vy|-|Vx ∩ Vy| => |Vx|+|Vy|=|Vx U Vy|+|Vx ∩ Vy|

We can rewrite the condition given by the problem as d(x)+d(y)>=n+k-2 => |Vx|+|Vy|>=n+k-2 => |Vx U Vy|+|Vx ∩ Vy|>=n+k-2 => n-2-R+C>=n+k-2

Therefore C>=k+R. Since R can be 0, C is at least k. *endzone dance*