Vertex connectivity of $K_n$ upon removal of edges of subgraph $C_n$ Consider graph $G$ = $K_n$ - $E(C_n)$ ($G$ is complete graph on $n$ vertices upon removal of edges of subgraph $C_n$). For every $n \ge 3$ find maximum $k$ such that $G$ is vertex $k$-connected.
I don't really know the way to approach this problem so here is some information (hopefully, everything said is true) i thought could be useful: 
After removing those edges we basically lower the $deg(v)$ for every $v$ $\in$ $G$ by 2, because this $C_n$ enters $v$ with 1 edge and exits $v$ with 1 edge. Since $deg(v)$ of every $v$ $\in$ $K_n$ is $n-1$, $deg(v)$ of every $v$ $\in$ $G$ is $n-3$.(Maybe a good base for use of Mengers theorem?)
Well for cases $n=3$, $n=4$:  $G$ is disconnected thus $k = 0$. For $k = 5$ it becomes interesting as $G$ is $C_n$ thus $k = 2$. (Maybe a good start for some kind of induction?)
Any help is highly appreciated. Thanks
 A: Let's say that $n \ge 5$ to avoid trivial cases, when $G$ is disconnected.
Hypotesis: $G$ = $K_n$ - $E(C_n)$ ($G$ is complete graph on $n$ vertices upon removal of edges of subgraph $C_n$). For every $n \ge 5$ $G$ is vertex $(n-3)$-connected.
We will try to show, that there are exactly $(n-3)$ disjoint paths between every two vertices $A,B \in G$. As already mentioned above, $ deg(v)$ of every $v$ $\in$ $G$ is $(n-3)$,what means that $(n - 3)$ is the maximum possible number of neighbours of $v$. Since every disjoint path must enter/exit $v$ from one of it's neighbours, we get and upper bound for such paths $(n-3)$.
If we can show that there are always $(n-3)$ disjoint paths between every two vertices $A,B \in G$ then by Menger's theorem $G$ is vertex $(n-3)$-connected, thus our hypotesis was correct.
Menger's theorem (for completness, source: Wikipedia)
Let G be a finite undirected graph and $x$ and $y$ two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for $x$ and $y$ (the minimum number of vertices whose removal disconnects $x$ and $y$) is equal to the maximum number of pairwise vertex-independent paths from $x$ to $y$.
Let's denote $X_A$ to be set of vertices $u$ such that edge $(u,A) \in E(_K(_n))$ but $(u,A) \notin E(G)$. Those are vertices that used to be connected to $A$ with edge in $K_n$ but aren't connected to $A$ with edge in $G$.
We will discuss 3 possibilities of position of vertices $A$ and $B$:

*

*$|(X_A \cup X_B) \setminus$ {$A,B$}$|$= $2$.
This means, that $A$ and $B$ were neighbours. There are $(n-4)$ vertices in $G$ different from set $X_A \cup X_B$. Every of this edge is connected with edge with both vertices $A$ and $B$. So we get $(n-4)$ disjoint paths (for example, let's call one of such vertices u, every path like this is created by 2 edges $(A,u)$ and $(u,B)$). In the example graph those paths are coloured green, purple and orange. We know: $X_A$ = {$B,x$}, $X_B$ = {$A,y$}. We need need one extra path between $A$ and $B$. Apparently there is an edge between vertices $y$ and $A$ ($y$ is not contained in $X_A$) and vertices $x$ and $B$ ($x$ is not contained in $X_B$). Well there must always be an edge between such vertices $x$ and $y$ because they weren't lying on $C_n$ next to each other. So the last desired path consists of edges $(A,y),(y,x),(x,B)$ (blue colour).



*$|(X_A \cup X_B) \setminus$ {$A,B$}$|$= $3$ This means that there is one vertex lying on $C_n$ between $A$ and $B$. We can actually say that $|(X_A \cup X_B)$|= $3$ because $B \notin X_A$ and $A \notin X_B$. There are $(n-5)$ vertices in $G$ different from set $X_A \cup X_B \cup$ {$A,B$}. Every of this edge is connected with edge with both vertices $A$ and $B$. So we get $(n-5)$ disjoint paths (for example, let's call one of such vertices u, every path like this is created by 2 edges $(A,u)$ and $(u,B)$). In the example graph those paths are coloured green and orange. Next path is trivial : it's the edge $(A,B)$ (red colour). In fact, now we can choose the last desired path in 2 ways: $((A,y),(y,x),(x,B)$(this one is shown in the example graph - blue colour) or $((A,y),(y,z),(z,x),(x,B)$ (apparently, those are not disjoint). I think I had shown that it's really easy to prove that such paths exist and won't explain further.



*$|X_A \cup X_B|= 4$ Well, this means that sets $X_A$ and $X_B$ do not overlap.There are $(n-6)$ vertices in $G$ different from set $X_A \cup X_B \cup$ {$A,B$}. Every of this edge is connected with edge with both vertices $A$ and $B$. So we get $(n-5)$ disjoint paths (for example, let's call one of such vertices u, every path like this is created by 2 edges $(A,u)$ and $(u,B)$). Another path is the edge $(A,B)$. From this point, you already know how to denote those paths and prove they exist formally...

Final comment: As this was my first answer here on stackexchange and I have never done anything using latex, there might be some typos.If you got any comments, please contribute. It was really difficult and exhausting to provide legit formal proof like this (well i hope it's legit haha), but I feel somehow satisfied and I hope this will help someone one day :-). I admire those people who are helping to solve thousands of problems here, and I hope I will be like you one day :-). If there is any native English speaker, please feel free to correct my mistakes.
