Let G = (V,E) be an edge-weighted connected graph, and T = (V,E\') be its minimu

Question

Let G = (V,E) be an edge-weighted connected graph, and T = (V,E') be its minimum, and e be any edge in T.

a) Consider the graph T' = (V, E - {e}). How many connected component(s) does T' have? Prove your answer from the definition of a connected component.

b)  Let C' be any connected component in T' and let E" ? E be the set of edges connecting C' and V-C'. That is, E" = {(x,y):(x,y) ? E, x ? C', y ? V-C'}. This edge set E" is said to be the cut (C', V-C') of G. Prove that the given edge e has the minimum weight among all in the cut (C', V-C').

.

Explanation / Answer

Solution:

a)

The definition of MInimum spanning tree is that:

It is a connected graph with n-1 number of edges which are the smallest n-1 edges of the graph (if not creating a cycle in the MST), where n is number of vertices in the graph.

Since T is the minimum spanning tree of the Graph G then this means that it doesn't have any cycle in it and it is a connected graph, so after removing e from Tthe T' will have two components in it.

b)

According to the definition the set C' and V-C' are the one who are connected as bipartite graph.

since it is mentioned that they are connected with the set of vertices (x, y) are connected such that x C' and y V-C', and vertex y is not in C'

this means C' and V-C' are two different disjoint sets.

so now the MST will have only one edge from all the sets of (x, y) in the tree, which will be the smallest one.

Which proves that the edge e which is cutting and dividing the graph into two components will be the smallest weight edge among (C, V-C')

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.