定理8.11:V的子集I是G的独立集当且仅当V是 G的点覆盖。 证明:(1)V的子集I是G的独立集。 由独立集的定义,I中任意两个点不相邻, G中每条边至少有一个端点不在中,即在V中, G中每条边至少有一个端点在V中, V为G的点覆盖。 (2)V是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在中 I中任意2点不相邻,即是独立集。定理 8.11：V的子集I是G的独立集当且仅当V-I是 G的点覆盖。 证明：(1) V的子集I是G的独立集。 由独立集的定义, I 中任意两个点不相邻， G中每条边至少有一个端点不在I中，即在V-I中， G中每条边至少有一个端点在V-I中， V-I为G的点覆盖。 (2) V-I是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在I中 I中任意2点不相邻，即I是独立集