Hacker News Reader

2 groups of 3 mutual friends is a different graph than 3 pairs of friends

No, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.

I understand that. That's the encoding of being "connected".

Where did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".

In this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way.

The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.