I am having trouble on this homework question:

Given a K-connected graph $G$ K_n on $n$ vertices where $n \geq 2$, show that the size of the smallest edge separator is the same as the size of the smallest vertex separator, and is size $n-1$.

(the graph K_n is a fully connected graph on n vertices)

Intuitively I can see that to separate a vertex $x$, you must remove all $n-1$ edges attached to $x$, because if even one remains then there will still be a path to $x$from any other vertex through that edge, so $n-1$ edges should be removed. Again for vertex separator if you don't remove all vertices but one, the remaining vertices will all be connected by the property of $G$ being K-connected.

My problem is how to get this across mathematically, one idea I had for the edge separator was to first show that the separator must be of at least size $n-1$ and then show it is at most size $n-1$ thus meaning it must be exactly $n-1$ but again I'm not sure how fully go about this.

Any tips to get me started would be great, thanks!

  • $\begingroup$ Is there some relationship between $K$ and $n$ that you aren't stating? Or, have you accidentally used $n$ in several places where you meant $K$? $\endgroup$ – Nick Peterson Nov 25 '15 at 17:41
  • $\begingroup$ Ah you are right, I thought I was making more sense by talking about it in terms of $n$ but I realise now I didn't need to, I will edit it accordingly. $\endgroup$ – Tim Hodgkin Nov 25 '15 at 20:42
  • $\begingroup$ What exactly is your definition of a separator? For instance, for vertex sets $A,B \subseteq V$ with $A \cap B = \varnothing$ you can define a vertex separator for $A$ and $B$ as a subset $S \subseteq V \setminus (A \cup B)$ that separates $A$ and $B$, and such a set might not always exist. If you want to separate a single vertex from the rest of the graph, you must necessarily disconnect it from all its neighbours, so now the problem is trivial... $\endgroup$ – Josse van Dobben de Bruyn Nov 26 '15 at 9:41
  • $\begingroup$ An edge separator is a set of edges that leave at least 2 separate components behind when removed, and a vertex separator is the same with vertices instead of edges. $\endgroup$ – Tim Hodgkin Nov 26 '15 at 11:39
  • $\begingroup$ Okay, so there does not exist a vertex separator for $K_n$, right? Whichever set of vertices is removed, the remaining graph is always connected (and isomorphic to a complete graph on $m$ vertices for some natural number $m \leq n$). $\endgroup$ – Josse van Dobben de Bruyn Nov 27 '15 at 16:33

Here is a hint for the edge separator: write $K_n = (V,E)$, where $V$ denotes the set of vertices and $E$ the set of edges. Now suppose that the removal of some edge set $F \subseteq E$ leaves the graph disconnected, then we can choose a partition $V = A \cup B$ of the vertices (with $A \cap B = \varnothing$, $A \neq \varnothing$ and $B \neq \varnothing$) so that there are no edges going between $A$ and $B$ in the graph $G \setminus F$. Count the number of edges between $A$ and $B$ in the original graph $K_n$ and so some calculus; this gives a lower bound on $|F|$.

I am currently under the impression that there does not exist a vertex separator. If a vertex separator were to be defined as a vertex set $U \subseteq V$ so that the removal of $U$ leaves the graph disconnected (rather than leaving 2 or more components), then $V$ is the only vertex separator, as the empty graph is disconnected. But this set has cardinality $n$, not $n-1$...


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.