題組內容

二、給定一個權重圖（weighted graph），G =(V, E, w)，假設 V = {1, 2,...,n}，且每個邊（edge）e 的權重 w(e)都是正整數。令 l(v)為以 v 為端點的所有邊中權重最小的邊。將這些邊集合起來稱作 L，也就是（每小題 5 分，共 20 分）

⑴假設每個邊的權重都不相同。請證明由 L 中這些邊所構成的子圖（edge induced subgraph）G[L]沒有迴圈。