Why do we divide by 2?
Each handshake necessarily involves two people. Let's call the first person A, the second person B, etc. We don't know with which three people A shook hands, but we do know: whoever those three people were, the handshake with A counts as one of A's three handshakes and also counts as one of that other person's three handshakes. Say A shook hands with, for example, E - that handshake would be one of A's three handshakes and one of E's three handshakes. Thereby, regardless of who is shaking whose hand, each handshake is counted twice. That's why we have to divide by two.