1.设无向图G（u，v）中无鼓舞顶点，则G的极大点独立集都是G的极小支配集。逆命题不成立

理解：设V*为G的一个极大点独立集，那么对于那些不属于V*的点，他们肯定跟V*里的某个点相连（否则就不是极大了），因此V*肯定是个支配集。而又由于V*里，全部的点都是独立的，所以。把不论什么一个点拿出V*后，该点跟V*中剩余的全部的点都没法相连。即无法被支配。

故在该条件下V*为极小支配集。

2 一个独立集是极大独立集，当且仅当它是一个支配集。

理解：设V*为G的一个极大点独立集，那么对于那些不属于V*的点，他们肯定跟V*里的某个点相连（否则就不是极大了），因此V*肯定是个支配集。

3 设无向图G(V,E)中无孤立点，顶点集合V*被包括于V，则V*是G的点覆盖。当且仅当V-V*是G的点独立集。

理解：设T为V-V*（即V*关于V的补集），那么，若T为点独立集，则说明，没有某条边的两个相关点都属于T。故全部的边的两个相关点中，至少有一个属于T的补集，即V*。则V*为G的点覆盖集。 反过来。若V*是G的点覆盖。则说明，全部的边的两个相关点中，至少有一个属于V*，因而在T中，不可能存在两个相邻的点，即T为点独立集。

推论：设G是n阶无孤立点的图。则V*是G的极小（最小）点覆盖，当且仅当V-V*是G的极大（最大）点独立集，从而有：点覆盖数+点独立数=n。

4 二部图的最小点覆盖=最大匹配

理解：由于我们要尽可能用少的点去覆盖全部的边，所以，对于二分图的x部，y部中的随意一部而言，一条边尽可能少的跟点相连（对于随意一部，最好仅仅跟一个点相连），那么这就是匹配问题了。可是我们又要把全部的边都覆盖进去。所以要求最大匹配，而当我们求得最大匹配后，其它边都能被最大匹配的点覆盖（若存在不能被覆盖的边，那么就不是最大匹配了）。