Determine the vertexconnectivity and the edgeconnectivity of

Determine the vertex-connectivity and the edge-connectivity of each of the following graphs. Give sufficient reasons for your answers. (a)The cycle C_n. (b) The path P_n. (c) The complete bipartite graph K_m,n

Solution

a)For cycle C_n

vertex connectivity is n-1 ,because in a complete cycle of n vertices any two vertices are connected so n-1 vertices should be removed to make graph disconnect.

edge connectivity is n-1, because we need to remove all the edges that are connected to a particular vertex to make graph disconnected ,by removing least no of edges

b)For the path P_n

vertex connectivity is 1 ,as removing of one vertex is sufficient to make graph disconnect

edge connectivity is 1 ,as removing of one edge is sufficient to make graph disconnect

c)For bipartite graph K_m,n

vertex connectivity is minimum of m,n

edge connectivity is minimum of m,n