Explore BrainMass

K-connected graph proof

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

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.