I am trying to solve this assignment:
Find all $n \in \mathbb{N}$ for which the following is true: By removing two random edges from graph $K_n$ we create at most $(n - 3)$-connected graph.
I would say that it is true for all odd $n$, but I got to this conclusion just by drawing some graphs and highlighting the disjunct paths in them in accordance with Menger's theorem. Still - I am not exactly sure about it, nor have I been able to formulate a solid proof. Can someone please give me a little push?