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.
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.