Out of a group of 10 people, what is the maximum number of FST's that exist?

[Don Leon]

Ever wonder how Facebook suggests "People you may know"?

One of the first (and simplest) algorithms that is used, is to look for strangers with whom you have many mutual friends.

For example, if you and Colin are not friends on Facebook yet, but both of you are friends with Belinda, then {you, Belinda, Colin} form a Friend Suggestion Triangle (FST).
The more FST's that exist, the more strangers Facebook can suggest with greater confidence that you might know them.

Out of a group of 10 people, what is the maximum number of FST's that exist?
Brian, 36 is not true, maybe you can try to rethink about your answer? thanks

[Brian]

If we have one person who is friends with the other 9,
and no friendships exist amongst these other 9, then a FST
exists between each of the C(9,2) = 36 pairings of 2 of these
9 people along with the original (popular) person. So I think
that 36 is the maximum number of FSTs.

Edit: Yes, I was way off. I believe the maximum is 100.
Divide the 10 people into 2 groups of 5. In each group,
no one knows anyone else, but each of them knows
every member of the other group. So each of the 10
people act as the 'primary vertex', (by which I mean
the person who knows each of the other two in the FST),
to C(5,2) = 10 FSTs. (The C(5,2) term comes from
choosing 2 of the 5 people in the other group.)

Since there can only be one 'primary vertex' in any FST,
each of these 10*10 = 100 FSTs will be unique.

I'm not sure how to prove that this is the maximum,
but I can't find any configuration that results in more FSTs.

Edit #2: In general, for n = 2m people there is a maximum
of (m^2)*(m - 1) FSTs, and for n = 2m + 1 there is a
maximum of (m/2)*(2m - 1)*(m + 1) FSTs.

So, for example, with n = 10 = 2*5, we have m = 5,
and thus a maximum of 5^2*(5 - 1) = 100 FSTs.

For n = 9 = 2*4 + 1, we have m = 4, and thus a
maximum of (4/2)*(2*4 - 1)*(4 + 1) = 2*7*5 = 70 FSTs.

As m gets very large, the maximum number of FSTs
goes roughly as m^3.