(a) Suppose G = (V, E) is any undirected graph and (S, V-S) is a cut with zero cut edges in G. Prove that if we pick two arbitrary vertices u ES and v EV - S, and add a new edge (u, v), in the resulting graph, there is no cycle that contains the edge (u, v).
(a) Suppose G = (V, E) is any undirected graph and (S, V-S) is a cut with zero cut edges in G. Prove that if we pick two arbitrary vertices u ES and v EV - S, and add a new edge (u, v), in the resulting graph, there is no cycle that contains the edge (u, v).
Related questions
Question
I need a proof as a solution for both of these questions.

Transcribed Image Text:(a) Suppose G = (V, E) is any undirected graph and (S, V-S) is a cut with zero cut edges in G. Prove
that if we pick two arbitrary vertices u ES and v € V - S, and add a new edge (u, v), in the resulting
graph, there is no cycle that contains the edge (u, v).

Transcribed Image Text:(b) Suppose G = (V, E) is an undirected graph with weight we on each edge e. Suppose f is an edge in
G with weight strictly smaller than all other edges. Prove that every minimum spanning tree (MST)
must contain f.
Expert Solution

This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
