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!
Best Answer
This essentially amounts to finding the minimum number of edges a connected subgraph of $K_n$ can have; this is your 'boundary' case.
The 'smallest' connected subgraphs of $K_n$ are trees, with $n - 1$ edges. Since $K_n$ has ${n \choose 2} = \frac{n(n-1)}{2}$ edges, you'll need to remove ${n \choose 2} - (n - 2)$ edges. If you remove strictly fewer edges, you would still have at least $n - 1$ edges, possibly leaving a connected tree.
That's a lot of edges! As you can see, $K_n$ is quite connected.