将引起的图形宽度减少被删除的边缘

Question

我想知道如果我从无向图中删除边缘，它的感应宽度会减少吗？如何证明它或我在哪里可以找到它的证明？谢谢！

Answer 1

从图形中删除边缘不会增加其引起的宽度。

给定一个顶点排序<，边集，我们的工会在确定其诱发的宽度是

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

这是图形减去一个边缘的一个子集，因为每个u, v, w元组证人纳入uv也适用于原始图。