Problem: At a certain orphanage, every pair of orphans are either friends or enemies.
For every three of an orphan's friends,
an even number of pairs of them are enemies.
Prove that it's possible to assign each orphan two parents
such that every pair of friends shares exactly one parent,
no pair of enemies shares any parents,
and no three parents are in a love triangle (where each pair of them has a child).

Solution: Of course, we consider the graph with vertices as children and edges as friendships.
Consider all the maximal cliques in the graph.

\begin{claim*}
Every vertex is in at most two maximal cliques.
\end{claim*}

\begin{proof}
  Indeed, consider a vertex $v$ adjacent to $w_1$ and $w_2$,
  but with $w_1$ not adjacent to $w_2$.
  Then by condition, any third vertex $u$
  must be adjacent to exactly one of $w_1$ and $w_2$.
  Moreover, given vertices $u$ and $u'$ adjacent to $w_1$,
  vertices $u$ and $u'$ are adjacent too.
  This proves the claim.
\end{proof}

Now, for every maximal clique we assign a particular parent to all vertices in that clique,
adding in additional distinct parents if there are any deficient children.
This satisfies the friendship/enemy condition.
Moreover, one can readily check that there are no love triangles:
given children $a$, $b$, $c$ such that $a$ and $b$ share a parent
while $a$ and $c$ share another parent,
according to the claim $b$ and $c$ can't share a third parent.
This completes the problem.

\begin{remark*}
  This solution is highly motivated for the following reason:
  by experimenting with small cases,
  one quickly finds that given some vertices which form a clique,
  one \emph{must} assign some particular parent to all vertices in that clique.
  That is, the requirements of the problem are sufficiently rigid
  that there is no room for freedom on our part,
  so we know \emph{a priori} that an assignment based on cliques
  (as above) must work.
  From there we know exactly what to prove,
  and everything else follows through.

  Ironically, the condition that there be no love triangle
  actually makes the problem easier, because it tells us exactly what to do!
\end{remark*}