Thread: Problems about connectivity

Hi,

Can you help me to prove the following statements?

(1) Let G be a graph. Prove that if d(G)=p-2, then K(G)=d(G)
(2) Prove that if G is connected, then K(G)=1+min{K(G-v):v is a vertex of G}

In any case, d(G) is the minimum vertex degree, p the number of vertices and K(G) the minimum k for which G has a k-vertex cut

A lil' tip. k(G) is less than or equal to d(G) for all graphs