假如每人就是恰好認識三人,如果有四人彼此認識而不認識其他人,那麼這個圖是不連通的,將這四人分在兩組,那麼他們所在組只認識一人。如果是三人彼此認識,然後他們再認識不同的人,那麼只要將一人分在不同組即可,他們認識的至少有兩人彼此不認識(否則又是四人彼此認識),將兩個人認識的分在另一組。最後剩下沒有四人彼此認識,也沒有三人彼此認識,剩下的連通的可組成二部圖分在兩邊,同一邊的沒有一個認識。