关于图中的二分集和独立集

Question

假设有一个二分图。那我可以说从V的两个二分划分中，基数最大的划分是该图的最大独立集吗？

因为，二分图中的所有边都是切割边（穿过 b/w 两个分区），所以没有更多的边可以处理，即没有更多的节点可以添加到最大基数分区边的两个端点都在同一个分区中，这违反了独立集的属性。

如果我们能像这样得到最大独立集，那么对于非二分图，我可以对图进行 2 着色，然后从两个分区中删除所有坏边（及其 2 个端点）和将剩余的最大基数分区称为图的最大独立集？

Answer 1

对于任意二分法（即，将顶点集划分为两个独立的集），情况并非如此。例如，一个有两个顶点且没有边的图可以分成两个单集，但最大独立集的大小为 2，而不是 1。