Proof about Signed Complete Graph Let a complete graph $K_n$ in which nodes represent people. For each pair of people, we label their relationship + or -. + indicates the two people are friends while - indicates they are enemies. A labeling is balanced if it has the property that for every set of three people, if we consider the three relationships between them, either all three are labeled +, or exactly one is labeled +.
Prove that in any balanced labeling either everyone is friends with everyone, or people can be partitioned into two groups, A and B, such that all pairs in A are BFFs, all pairs in B are BFFs, and everyone in A is an enemy of everyone in B.
The first case is trivial. For the latter case, consider a - edge. I should show that one end leads to a set, and the other end leads to another set. However, I am not sure how to begin. Any help is appreciated. Thank you.
 A: The balanced labeling condition implies that friendship is transitive. It is also inherently symmetric, so if we consider everyone to be friends with themselves, it is an equivalence relation.
Therefore the people can be partitioned into equivalence classes: several groups such that everyone is friends with everyone in their own group, and nobody else.
Finally, if we could take three people from different groups, the triangle they induce would not be balanced; therefore there can be at most two groups.

Alternatively, to complete the proof in the way you suggested, suppose $v$ and $w$ are a pair of enemies. First, show that every other person $x$ is friends with exactly one of $v$ or $w$, by considering the triple $\{v,w,x\}$. We can now let $A$ be the set of all people friends with $v$ and let $B$ be the set of all people friends with $w$, to get a partition. To show that this partition is a split into two enemy factions, we must check that:

*

*If $x, y \in A$, then $x$ is friends with $y$.

*If $x, y \in B$, then $x$ is friends with $y$.

*If $x \in A$ and $y \in B$, then $x$ and $y$ are enemies.

Each of the three can be done by looking at the triple $\{v, x, y\}$, in which we already know the status of the pairs $vx$ and $vy$, and can therefore infer the status of the third pair $xy$.
