Do the NP: find the largest clique

Mathematica, 34 bytes

Tr[1^#&@@FindClique[#<->#2&@@@#]]&  

Basically FindClique does the job and "finds a largest clique in the graph g."
All the other stuff is converting input-list into graph

Input

[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}]

Output

4

Input

[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}]

Output

6

thanx @Kelly Lowder for -10 bytes


Jelly, 20 bytes

ŒPẎ€µQL’=ċЀ`ẠµÐfṪQL

Try it online!

Of course this doesn't deserve the million :p

This would've beat Pyth, if not for the µ(...)µ and 2-byte Ðf.


Jelly,  15 18  16 bytes

+3 bytes to fix bugs in my method.
-2 bytes thanks to miles (noting that n×(n-1)÷2 = nC2)

ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ

A monadic link taking the list of friendships (edges) and returning an integer.

Try it online! forms the power-set of the edges in memory so is inefficient both in space and time (yep,that's O(2n) folks)!

How?

ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges  e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ          - tighten                              [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
 Q         - de-duplicate (gets unique ids)          [1,3,2,4]
  L        - length (get number of people involved)  4
   ©       - (copy to the register)
    c2     - combinations of 2 (z-choose-2)          6
       L   - length (of edges)                       6
      ⁼    - equal?                                  1
         ® - recall value from register              4
        ȧ  - logical and                             4
           - (Note: the number of edges of a clique of size n is n*(n-1) and we're
           -  guaranteed no repeated edges and that all edges are two distinct ids)

ŒPÇ€Ṁ - Link: list of lists, edges
ŒP    - power-set (all possible sets of edges (as lists))
  Ç€  - call last link (1) as a monad for €ach
    Ṁ - maximum