將引起的圖形寬度減少被刪除的邊緣

Question

我想知道如果我從無向圖中刪除邊緣，它的感應寬度會減少嗎？如何證明它或我在哪裏可以找到它的證明？謝謝！

Answer 1

從圖形中刪除邊緣不會增加其引起的寬度。

給定一個頂點排序<，邊集，我們的工會在確定其誘發的寬度是

{uv | exist vertices u, v, w such that u, v adjacent to w and u, v < w}. 

這是圖形減去一個邊緣的一個子集，因爲每個u, v, w元組證人納入uv也適用於原始圖。