2012 AMC 10A Problem 23

We case on the value of friends that each person has. This value ranges from $1$ to $4$, since the graph is neither empty nor complete. Note that the cases for $1$ and $2$ friends correspond with the case for $4$ and $3$ friends, since choosing who are friends determines who are not friends. Case $1:$ everyone has $1$ friend This means that the $6$ people must split up into $3$ pairs where the people in each pair are friends. There are $5$ choices for the friend for the first person. This leaves $4$ people remaining. There are then $3$ choices for the friend of the next unpaired person. The remaining $2$ people are then forced to be friends. Therefore, there are $3 \cdot 5 = 15$ possibilities for this case. Case $2:$ everyone has $2$ friends There are two possibilities for this case. There could be two triples where everyone in a triple is friends with each other. For this possibility, there are $\binom{6}{3} = 20$ ways to choose the people in the first triple. We have to divide by $2$ since we can swap the pairs. This gives us $20 \div 2 = 10$ configurations. The second possibility is that the friends form one $6$-cycle. Every ordering of the six people around a cycle gives such a graph. Each graph is counted $6$ times by the choice of starting person and $2$ times by the direction of traversal, so there are $\frac{6!}{6\cdot2}=60$ distinct $6$-cycles. Together with the $10$ pairs of triangles, this case has $10+60=70$ configurations. The total number of arrangements is then $$2(15 + 70) = 170.$$ Thus, B is the correct answer.