Show that if the diameter of an undirected graph is $d$ then there is some set
$S\subseteq V$ with $|S| \leq \frac{n}{d-1} $ such that removing the vertices in S from the graph would break it into several disconnected pieces. The diameter $d$ is measured in edges and the graph is undirected and unweighted. $n$ is the number of vertices in the graph.
First my intentions were to use induction on this claim in order to prove it but then when I tried to make the base case I saw that it is not true in some cases.
For example: a graph with $|V|=5$ and $d=4$ that looks like this:
+---+---+---+---+
If I try the above formula here I will get that $|S|\leq 1.667$ which is obviously not true because there are 3 components which can belong to $S$.
Is it possible to prove the above claim? if so would induction be a good method?
I am not sure induction can be helpful on this problem (but you're welcome to try !).
You can make use of Menger's Theorem, which states the following :
"Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal disconnects x and y) is equal to the maximum number of pairwise vertex-independent paths from x to y."
So, take $x$ and $y$ at maximum distance, i.e. $d(x, y) = d$. Let $k$ be the minimum number of vertices whose removal disconnects $x$ and $y$. We then know there is a set $S$ with $|S| = k$ that disconnects $G$.
By Menger, there are $k$ vertex disjoint paths from $x$ to $y$, each path containing at least $d - 1$ distinct vertices not in any of the other paths ($d - 1$ as all these paths must be of length at least $d$). So the number of vertices of $G$ is $n \geq k(d - 1) = |S|(d - 1)$. Therefore, $|S| \leq \frac{n}{d-1}$ and $S$ disconnects $G$.