通常的想法是：如果图是一棵树，那么通过对顶点进行双色染色，并从更频繁的颜色中选取顶点，就可以轻松找到大小为\(\lceil\frac{n}{2}\rceil\)的独立集合。否则，图就是循环的。让我们得到一个没有任何边“穿过”的循环。换句话说，它没有任何一对不相邻的顶点由边连接。如果它的长度最多