Despite my other comment, I actually think anyone smart should be able to answer the complete graph question, especially if you walk through a couple smaller examples. You don't need a class on graph theory to recognize the pattern 1+2+...+(n-1).
You're right, and that's why I asked if nobody really "brute-forced" it, but one probably never knew about meshes and never wondered about the # of links in them until one has had someone describe it to them. My objection, if you will, is that the stimulus for such subjects comes mainly from a class on graph theory (sure, there are exceptions).
By the time the interviewee would be desperate enough to brute force it [were they in a room by themselves], they get so embarassed they say they don't know and they'd rather move on.
You shouldn't need graph theory to simply reason your way to an answer using a bit of thought and some basic arithmetic. Anybody how looks at a problem and goes "oh that looks like X and I don't know X" and then shut of their brains is probably not a great hire.
And honestly, are you telling me that nobody answered in "however long it takes", ie. nobody just counted them on paper?