The social graph example suggests that a transitive closure is required, remove all edges where both extremities have the same label (same first name), and then the solutions would be finding all Maximum Cliques: this can be solved using the well known Bron–Kerbosch algorithm.