Edges may be removed from the graph that follows so that is becomes a spanning tree. Identify a set
Of edges that can be removed to accomplish this.
A)GH and FG
B)GH and HI
C)EF and EH
D)HI and FI

Question

Edges may be removed from the graph that follows so that is becomes a spanning tree. Identify a set
Of edges that can be removed to accomplish this. 
A)GH and FG 
B)GH and HI 
C)EF and EH 
D)HI and FI

Quizplus · Accepted Answer

In order to make the given graph a spanning tree, we need to remove exactly one edge from each cycle present in the graph. The cycles present in the given graph are: ABGHFA, BCDHEF, and EFGHI.

Option A: Removing edges GH and FG will break the cycle ABGHFA, but the cycle EFGHI will remain as it is. So, option A is not a correct choice.

Option B: Removing edges GH and HI will break the cycle EFGHI and the cycle ABGHFA will remain as it is. So, option B is a correct choice.

Option C: Removing edges EF and EH will break the cycle BCDHEF, but the cycle EFGHI will remain as it is. So, option C is not a correct choice.

Option D: Removing edges HI and FI will break the cycle EFGHI, but the cycle ABGHFA will remain as it is. So, option D is not a correct choice.

Therefore, the best choice is B, GH and HI.

Edges May Be Removed from the Graph That Follows So