# K-connected graph proof

Not what you're looking for? Search our solutions OR ask your own Custom question.

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 ad1c9bdddfhttps://brainmass.com/math/graphs-and-functions/k-connected-graph-proof-98567

#### Solution Preview

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 ...

#### Solution Summary

This is a proof regarding a k-connected graph.

$2.49