假如每人就是恰好认识三人,如果有四人彼此认识而不认识其他人,那么这个图是不连通的,将这四人分在两组,那么他们所在组只认识一人。如果是三人彼此认识,然后他们再认识不同的人,那么只要将一人分在不同组即可,他们认识的至少有两人彼此不认识(否则又是四人彼此认识),将两个人认识的分在另一组。最后剩下没有四人彼此认识,也没有三人彼此认识,剩下的连通的可组成二部图分在两边,同一边的没有一个认识。