I am having trouble with my homework in graph theory. Someone can help me?
Let v1,v2 ,...,vk be k distinct vertices of a K-connected graph G. Let H be the graph formed from G by adding a new vertex w of degree k that is adjacent to each of v1 ,v2 ,...,vk . Show that κ(H) = k
Thatnk you :)
We assume $G$ has more than $k$ vertices and is $k$-connected. To say that a graph $G$ is $k$-connected means that we can remove any $k-1$ vertices from $G$ and still have a connected graph.
So, to show that our new graph $H=G+w$ is $k$-connected also, we have to show that $H-V_{k-1}$ is still a connected graph, where $V_{k-1}$ represents a vertex-cut-set of $k-1$ vertices.
Now we have two cases: either $w \in V_{k-1}$ or $w \notin V_{k-1}$.
If $w \in V_{k-1}$, then we have $H - w - V_{k-2} = G - V_{k-2}$, which we know is connected.
If $w \notin V_{k-1}$, we know that $w$ is then connected to some vertex of $G$, so the remaining graph $H-V_{k-1}$ is connected. This is because we connected $w$ to $v_1,v_2,...,v_k$, but only removed $k-1$ of them.
So, since $H$ remains connected whenever we remove fewer than $k$ vertices, we can say it is $k$-connected.