I do not think I am understanding the definition above. If I start out with a graph $G$ and two non-adjacent vertices $x$ and $y$ then to obtain $G^*$ I keep adding edges to $G$. I have tried looking at several examples and I keep ending up with a complete graph. How is it possible to end up with a minimal $G^*$ that isn't complete?
Thank you.
The text here can be a bit confusing, since there are two separate but related issues. The first is the definition of $k$-stable, which ends at "has it also". The next assertion, beginning at "It is easily seen", is a general statement regarding graphs, and is independent of $k$-stability.
To see this general statement, suppose there are two minimal graphs $G_1$ and $G_2$ containing $G$ such that $d_{G_i}(x) + d_{G_i}(y) \le k-1$ for $xy \notin E(G_i)$, for $i \in \{1,2\}$. Then $H=G_1 \cap G_2$ certainly contains $G$, since both $G_1$ and $G_2$ contain $G$. Moreover, for any vertices $x$,$y$ in $H$ such that $xy \notin E(H)$, either $xy \notin E(G_1)$ or $xy \notin E(G_2)$ is true, possibly both. Thus for some $i \in \{1,2\}$, we have $d_H(x) + d_H(y) \le d_{G_i}(x) + d_{G_i}(y) \le k-1$. Hence $H$ satisfies the degree condition and contains $G$, and is a subgraph of both $G_1$ and $G_2$. Since $G_1$ and $G_2$ are minimal graphs satisfying these properties, we must have $G_1 = H = G_2$, showing that this minimal graph is unique.
So if this statement is independent of $k$-stability, why is it here? Because the definition of $k$-stability ensures that a graph $G$ has $k$-stable property $P$ iff the graph $C_k(G)$ does.
Regarding examples where $C_k(G)$ is not complete, the null graph is its own $C_k(G)$ for all $k \ge 1$. A less trivial example is the complete bipartite graph $K_{2,n}$ for $n \ge 3$. For $5 \le k \le 2n$, $C_k(K_{2,n})$ is just $K_{2,n}$ with an edge added between the two vertices of the small partition.