设最小覆盖数为k,则m1,m2,..mk对应每次覆盖的顶点的数目，显然有m1+m2+...+mk=N(顶点总数)，再有连接x个顶点的迹的长度为x-1,所以最小覆盖所包含的变得数目为(m1-1) + (m2 - 2) + ... +　(mk － 1） ＝ N － k
即：最小覆盖数＝顶点数－最小覆盖中的边数