Given the complete graph on $n$ vertices $K_n$, what is the smallest number of edges you can remove in order to separate the graph into two disjoint subgraphs? I consider vertices without edges to be perfectly kosher subgraphs.
EDIT: It seems the answer might be $n-1$. A more interesting question that I actually might be more useful to me is the smallest number of edges you can remove while keeping the degree of every vertex positive in order to separate the graph into two disjoint subgraphs.
For example, in $K_3$, if you remove any two edges, you are left with two vertices connected by an edge and a lone vertex. In $K_4$, you can remove any three edges that share a vertex.
I am interested in this result so I can prove a fact about the connectedness of a graph produced by a set of preferences (non necessarily transitive preferences). Any help appreciated!