Homework SourseGraph Theory show that if kappaprimeG k 2 then the deletion
Graph Theory: show that if kappa-prime(G)= k >= 2, then the deletion of k edges from G results in a graph with at most 2 components.
Graph Theory: show that if kappa-prime(G)= k >= 2, then the deletion of k edges from G results in a graph with at most 2 components.
Solution
Kappa prime is nothing but edge connectivity of the graph. It gives a number which represents the number of edges to be removed from the graph G to make the graph G no longer connected.
Any graph G will have kappa prime greater than 1 if it doesn\'t have any pendant vertex (Vertex with degree 1 in an undirected graph).
Let us prove the theorem by example.
Assume a triangle graph G with 3 vertices and 3 edges, edge connectivity(kappa prime) is 2, since 2 edges needs to be removed to disconnect the graph.
When 2 edges are removed from the Graph, two vertices will be connected by one edge and one vertices will be disconnected. Hence there are atmost 2 connected components after removal of 2 (kappa prime) edges.
