Explore BrainMass

Explore BrainMass

    K-connected graph proof

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

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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

    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.