Let $H$ be the graph formed by adding a new vertex $w$ of degree $k$ and adjacent to each of $v_1,v_2,...v_k$. Show that $\kappa (H)=k$

378 Views Asked by At

Let $v_1,v_2,\ldots,v_k$ be $k$ distinct vertices of a $k$-connected graph $G$. Let $H$ be the graph formed bay adding a new vertex $w$ of degree $k$ and adjacent to each of $v_1,v_2,\ldots,v_k$. Show that $\kappa (H)=k$

I know that $G$ is a $k$-connected graph, so $\kappa (G) \geq k$, meaning if I remove fewer than $k$ vertices from $G$, then $G$ is neither disconnected nor trivial. Let $S=\{v_1,v_2,\ldots,v_k\}$.

Since $H$ is obtained by connecting $w$ to $S$, if we delete less than $k$ elements of $S$, $H$ is still connected and non-trivial. So if we want to get $H$ is disconnected or at least trivial, we need to delete all elements of $S$, thus $\kappa(H)=k$

This is the only reasoning I can think of, and I feel it is too sketchy. Any help will be appreciated.

1

There are 1 best solutions below

4
On BEST ANSWER

It is a bit too sketchy.

Let $T$ be an arbitrary separating set of $H$.

Case 1: $w\notin T$. If $\{w\}$ is a full component of $H-T$, then $T$ must contain at least all neighbours of $w$, so $|T|\geq k$. Otherwise the component of $H-T$ containing $w$ contains at least one other vertex, say $x$. Let $y$ be a vertex from another component of $H-T$. Now any path in $G$ avoiding $T$ immediately translates to a path in $H$ avoiding $T$. Since such a path in $H$ does not exist, it follows that it cannot exist in $G$, so $T$ separates $G$, so $|T|\geq k$.

Case 2: $w\in T$. Then $T-w$ separates $G$, so $|T-w|\geq k$, so certainly $|T|\geq k$.

Btw. this is called the "expansion lemma".