## six degrees of separation

Suppose there are 7 billion people in the world and that the network (graph) of their friendships is connected. To guarantee no more than 6 degrees of separation between any two people, what is a lower bound on the number of friendships each person needs to have?

We have log_{x} 7E9 = 6, or 7E9 = x^{6}, or ⌈x⌉ = 44 friends.