Hi thanks for the help on my previous problems

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.


???? i have no idea how u do these. please help.


Note: [] represents the greatest value function.


thanks again.