1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Do you want the smallest number of edges possible to disconnect $K_n$, or the smallest number of edges that will guarantee you'll disconnect $K_n$? $\endgroup$ – pjs36 Apr 20 '15 at 16:33
  • 2
    $\begingroup$ Removing the three edges adjacent to one vertex will separate $K_4$. $\endgroup$ – Christopher Apr 20 '15 at 16:33
  • $\begingroup$ @pjs36 I want the number of edges that will guarantee you'll disconnect $K_n$ in terms of $n$. A lower bound on the number of edges possible would be interesting as well, but not what I was trying to ask for. $\endgroup$ – Matt R Apr 20 '15 at 16:36
  • $\begingroup$ @user73985 This is a poor mistake. Will correct $\endgroup$ – Matt R Apr 20 '15 at 16:36
  • 2
    $\begingroup$ Removing $n-1$ can lead to a disconnected graph (by removing all the edges entering a vertex) and you need to remove at least $n(n-1)/2-n-1$ edges to be sure your graph is disconnected (otherwise a cycle is always possible with $n$ edges). $\endgroup$ – wece Apr 20 '15 at 16:43
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.