Given a $k$-connected graph $G$, let $G'$ be a graph obtained from $G$ by adding a new vertex $x$ and connecting it to any $k$ vertices of $G$. From first principles, show that $G'$ is $k$-connected.
I understand visually how this is, just don't know how to "show it from first principles".
$G$ is a graph that is k-connected means that removing less than $k$ vertices from $G$ and $G$ is still connected. Removing any set of vertices that do not contain $v$ from $G'$ of size less than $K$, doesn't disconnect $v$ from $G'$ as $v$ is connected to $k$ vertices in $G$. It doesn't disconnect $G$ as we removed less than k vertices. Now if you remove a set of vertices from $G'$ containing $v$ of size less than $k$, you don't disconnect $G$ as you removed less than $k$ vertices in $G$. so $G'$ is $k$ connected by definition.