Skip to main content
Computer Science

Return to Answer

added 35 characters in body
Source Link
Sorrop
Sorrop
  • 296
  • 3
  • 12

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? CouldMay it be the case that another edge in the cycle can play the 'role' of e in MST?

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? Could another edge play the 'role' of e in MST?

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? May it be the case that another edge in the cycle can play the 'role' of e in MST?

Source Link
Sorrop
Sorrop
  • 296
  • 3
  • 12

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? Could another edge play the 'role' of e in MST?