Team Selection Test Selection Test

Solution: Form a graph $G$ with the orphans as vertices and with an edge between two orphans if they are friends. Let $A_1, A_2, \dots$ be the maximal cliques of $G$; that is, every pair of orphans in $A_i$ is friends, and every orphan outside $A_i$ is an enemy of some orphan in $A_i$. We now have a sequence of lemmas.

Lemma 1. Any two maximal cliques intersect in at most one orphan.
Proof. Suppose for the sake of contradiction that $A_i$ and $A_j$ had intersection of size at least 2. We may choose orphans $u \in A_i$ and $v \in A_j$ such that $u$ is not friends with $v$; in particular, this means that $u \notin A_j$ and $v \notin A_i$. Then, taking two orphans $w, w' \in A_i \cap A_j$, notice that $w$ is friends with $u$, $v$, and $w'$ and that $\{u, w'\}$ and $\{v, w'\}$ are pairs of friends, but $\{u, v\}$ is not, contradicting the given. This proves the lemma. □

Lemma 2. Every orphan $v$ is in either 1 or 2 of the $A_i$.
Proof. No orphan is in none of the $A_i$, as any orphan forms a clique of size 1, which may be grown into a maximal clique. Suppose for the sake of contradiction that some orphan $v$ were in at least 3 maximal cliques. Without loss of generality, let these cliques include $A_1, A_2$, and $A_3$, and choose friends $v_1 \in A_1, v_2 \in A_2$, and $v_3 \in A_3$ of $v$.
For $i \neq j$, notice that $v_i \notin A_j$, as $A_j$ intersects $A_i$ in at most one orphan, which is $v$. Thus, $v_1, v_2$, and $v_3$ are distinct. If, say, $v_1$ and $v_2$ are friends, then $\{v, v_1, v_2\}$ forms a clique, hence is contained in some maximal clique $A$; then $A$ intersects both $A_1$ and $A_2$ in at least two orphans, implying by Lemma 1 that $A_1 = A = A_2$, a contradiction. Thus, there are no friendships between $v_1, v_2$, and $v_3$, which contradicts the given because $v$ is friends with each of them. □

Form a graph $H'$ with vertices $P_A$ the maximal cliques of $G$ and with an edge between two vertices if the corresponding cliques intersect. From $H'$, form the graph $H$ by attaching a leaf $P_{\{A,v\}}$ to the maximal clique $A$ for each orphan $v$ for which $A$ is the unique maximal clique containing $v$. Assign a parent to each vertex of $H$ and assign orphans to parents in the following way.

* If an orphan $v$ lies in only one maximal clique $A$, assign it to $P_A$ and $P_{\{A,v\}}$.
* If an orphan $v$ lies in two maximal cliques $A$ and $A'$, assign it to $P_A$ and $P_{A'}$.

This construction covers all cases by Lemma 2 and assigns each pair of parents at most one orphan by Lemma 1. By construction, if an orphan is assigned to two parents, there is an edge between those parents in $H$. Further, two orphans share a parent if and only if they share a maximal clique, meaning that they are friends. Finally, if $H$ contained a love triangle, then we would have three maximal cliques $A, A',$ and $A''$ with non-empty pairwise intersections at $v, v', v''$. Then $\{v, v', v''\}$ is a clique, hence lies in a maximal clique $A^*$ which intersects each of $A, A',$ and $A''$ with cardinality at least 2. By Lemma 1, this implies that $A^* = A = A' = A''$, a contradiction. Thus, $H$ has no love triangles, completing the proof.