AMC10 2012 A

Answer (B): This situation can be modeled with a graph having these six people as vertices, in which two vertices are joined by an edge if and only if the corresponding people are internet friends. Let $n$ be the number of friends each person has; then $1 \le n \le 4$. If $n = 1$, then the graph consists of three edges sharing no endpoints. There are 5 choices for Adam’s friend and then 3 ways to partition the remaining 4 people into 2 pairs of friends, for a total of $5 \cdot 3 = 15$ possibilities. The case $n = 4$ is complementary, with non-friendship playing the role of friendship, so there are 15 possibilities in that case as well. For $n = 2$, the graph must consist of cycles, and the only two choices are two triangles (3-cycles) and a hexagon (6-cycle). In the former case, there are $\binom{5}{2} = 10$ ways to choose two friends for Adam and that choice uniquely determines the triangles. In the latter case, every permutation of the six vertices determines a hexagon, but each hexagon is counted $6 \cdot 2 = 12$ times, because the hexagon can start at any vertex and be traversed in either direction. This gives $\frac{6!}{12} = 60$ hexagons, for a total of $10 + 60 = 70$ possibilities. The complementary case $n = 3$ provides 70 more. The total is therefore $15 + 15 + 70 + 70 = 170$.