Showing that $G$ contains a path such that it remains connected after removing the path.

Question

I am trying to solve the following problem from Bollobas's book.

Let $G$ be a connected graph with minimal degree $\delta(G) = k$ where $k \geq1$. Show that $G$ contains a path $(x_1,\ldots ,x_k)$ such that $G-\{x_1,\ldots,x_k\}$ is also connected.

So far what I have from the hint is the following :

Let $x_1\ldots x_l$ where $l \geq k+1$ be a longest path. Suppose the contrary, that $G- \{x_1, \ldots ,x_k \}$ is disconnected and let $y_0 y_1 \ldots y_m$ be a longest path in a component $C$ not containing $x_{k+1}$. Then $d_{C}(y_0) \leq m$ but $y_0$ cannot be joined to $k-m$ vertices $x_1, \ldots, x_k$

Then how do we proceed?

Answer 1

I'll slightly reword the solution.

The key idea is that we can remove $\{x_1,\dots x_k\}=X$ where $x_1,\dots , x_l$ is a path of maximum length.

We proceed by contradiction:

Assume $G-X$ has at least two connected components. Let $C$ be one that does not contain $x_{k+1},\dots,x_l$.

We are going to build a path of length larger than $l$, which is a contradiction.

To do this we take a vertex $z$ in $C$ that is connected to the maximum number of vertices in $X$ (notice that it is at least one because $G$ is connected) and we take a path of maximum length $y_1,y_2,\dots,y_m$ in $C$ that ends in $z$.

Notice that all neighbours of $y_1$ must be in $y_2,\dots, y_m$ and so $y_0$ has at least $k-(m-1)$ neighbours in $X$, it follows that $z$ also has at least $k-(m-1)$ neighbours in $X$.

We donote the first such neighbour by $x_n$ and we look at the path $x_n,x_{n+1},\dots,x_k$. This path has at least $k-m+1$ elements.

So now we are going to consider a new path that is gonna be super long ! Are you ready? It is the following:

$y_1,y_2,\dots,y_m, x_k,x_{k+1},\dots,x_l$

How many elements are here?

The first chunk has $m$ elements, the second chunk has at least $k-m+1$ elements and the last chunk has $l-k$ elements.

This means that it has at least $l+1$ elements. This my dear friends constitutes a contradiction.

Answer 2

Let $P= x_1 x_2,\ldots x_k \ldots x_l$ be a longest path in $G$ [note that there is such a path $P$ with $l \ge k+1$ vertices in $G$]. Let $C_1$ and $C_2$ be the two components of $G \setminus \{x_1,x_2 \ldots, x_k\}$ [i.e., remove from $G$ the first $k$ vertices of $P$ and assume that $G$ is disconnected with at least two components $C_1$ and $C_2$]. As $x_{k+1}, \ldots, x_l$ form a path we may assume $x_{k+1}, \ldots, x_l$ are in the same component so let us write wlog $x_{k+1}, \ldots, x_l \in C_2$.

Now, let us write $X=\{x_1,\ldots, x_k\}$. Now if there is a vertex $y \in C_1$ adjacent to all $k$ vertices then the path $P' = yx_1x_2 \ldots x_l$ is longer than $P$, so there cannot be such a $y$. So let $m$ be the maximum number of vertices in $X$ that a vertex $y \in C_1$ is adjacent to in $G$. Then $m <k$, and as each vertex in $C_1$ has degree at least $k$ in $G$ [because $G$ has minimum degree $k$] and is adjacent to only vertices in $C_1$ or $X$, it follows that

1. There must be at least $k-m+1$ vertices in $C_1$ and furthermore every vertex in $C_1$ is adjacent to at least $k-m$ other vertices in $C_1$ [so that each vertex $y \in C_1$ can have degree at least $k$].

2. As every vertex in $C_1$ has at least $k-m$ neighbors in $C_1$, every vertex $y \in C_1$ is the endpoint of a path $P_y \subset C_1$ with at least $k-m+1$ vertices.

3. Letting $y$ be a vertex adjacent to precisely $m$ other vertices in $X$. Then letting $j$ be the lowest integer such that $y$ is adjacent to $x_j$, it follows that $|\{x_j, x_{j+1},\ldots , x_k\}| \ge m$, and in particular, that $x_jx_{j+1}\ldots x_k$ is a path with at least $m$ vertices, and that $x_jx_{j+1} \ldots x_kx_{k+1} \ldots x_l$ is a path with at least $m + (l-k)$ vertices.

4. So let $y$ and $j$ be as in 3. and let $P_y = y_1y_2 \ldots y_{k-m}y$ be a path in $C_1$ with $k-m+1$ vertices ending at $y$, as guaranteed by 2. Then by 3. the path $P_y \cup x_j x_{j+1} \ldots x_k$ $=y_1y_2\ldots y_{k-m}yx_j \ldots x_k$ is indeed a path and has at least $k-m+1$ $+ m$ $=k+1$ vertices.

5. Thus also from 3. the following holds: $P_y \cup x_jx_{j+1} \ldots x_k x_{k+1} \ldots x_l$ $=y_1y_2\ldots y_{k-m}yx_j \ldots x_kx_{k+1} \ldots x_l$ is a path with at least $(k-m+1) + (m + l-k)$ $l+1$ vertices. Which is a contradiction.

Thus letting $X=\{x_1,\ldots, x_k\}$ be the first $k$ vertices of a longest path in $G$, it follows that $G \setminus X$ cannot have two components after all, and so $G \setminus X$ is connected.

---

A question was asked whether the vertices of the path with $k$ vertices were removed or the edges of the path. It doesn't matter as far as we are concerned the result holds either way. Note that $G \setminus X$ has one component, and as every vertex in $G$ has degree $k$, every vertex in $X$ is adjacent to at least one vertex in $G \setminus X$. So if one takes the graph $G \setminus X$ [which is one connected] and adds back each vertex $x$ in $X$ and the edges in $G$ between $x$ and $G \setminus X$ [but none of the edges between the vertices in $X$] then the resulting graph is connected too.