Vtyjkyuk

Prove that a simple graph $G$ with $n$ vertices, $n ge 2$; is complete if and only if $kappa(G)[textvertex connctivity]=n - 1$:

proof. n=1. It is trivially true. Suppose we assume result hols for $n=k$, We need to prove this result hold for $n=k+1$. Consider $K_k+1$ complete graph, removal of one vertex resuts $K_k$. We know that the $k-1$ vertex required to remove the graph disconnected. So, $kappa(K_k-1)=k-1+1=k$. Hence, by induction, result holds for every $nin mathbb N$. Am I correct?

For the statement $kappa(G) = n-1$ implies $G=K_n$, again use induction.

The base case is simple.

The induction hypothesis is then that if $G$ has $k-1$ vertices and $kappa(G) = k -2$, then $G = K_k-1$.

Now, take a graph $G$ with vertex connectivity $kappa(G) = k-1$. Pick an arbitrary vertex $v$, now $kappa(G-v) = k-2$ and has $k-1$ vertices, so that $G-v$ is the complete graph on $k-1$ vertices by the induction hypothesis. We can see that $operatornamedeg(v) = k-1$, because otherwise, the deletion of less that $k-1$ vertices from $G$ would disconnect $v$ from $G$, contradicting the fact that $kappa(G) = k-1$. Therefore, $G-v$ is $K_k-1$ and $v$ is connected to every vertex in it. Thus $G = K_k$.