3.17 Let v_1,v_2,...,v_k be k distinct vertices of a k-connected graph G. Let H be the graph formed from G by adding a new vertex of degree k that is adjacent to each of v_1,v_2,...,v_k. Show k(H)=k.
k(G)=is the vertex connectivity© BrainMass Inc. brainmass.com March 4, 2021, 7:24 pm ad1c9bdddf
Note: we name the vertex joining to each of v_1,v_2,...,v_k the new vertex.
Proof. By the definition of vertex-connectivity, we need to show that we need to remove at least k vertices from H to make H disconnected.
First of all, by the construction, we know that, if we remove v_1,v_2,...,v_k from H, then the new vertex joining ...
This is a proof regarding a k-connected graph.