
common neighbors
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+k2)/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 nvertex 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.