Olympiad problems which take moderately complicated graph-theoretic situations and re-express them as very complicated word problems make me sad. On the other hand, this is a cute little problem, once the nonsense is stripped away. Our starting data is a graph. Choose any vertex $v$ and consider the set of its neighbors. The condition is that among any three of these, there must be an odd number of edges (i.e., either 1 or 3). This is what is known at least some of the time as a "balanced graph" (or perhaps the complement of a balanced graph?). It's an old (and not difficult) result of Harary that such graphs have a very simple structure: they consist of either a single clique or two disjoint cliques. Now cover the graph by maximal cliques. The preceding paragraph shows that each vertex is contained in at most two of these maximal cliques and that two maximal cliques intersect in at most one vertex. Moreover, if two of these cliques share a vertex then there is no other maximal clique that shares a vertex with both of them. Now assign parents as follows: for each maximal clique, all the vertices in that clique get a single parent in common, and these parents are distinct for different cliques. For vertices in two maximal cliques, this determines both their parents; all other vertices are in a unique maximal clique. Assign one unused, distinct parent to each of these vertices. The resulting assignment has the desired properties.

Rephrase into graph theory; let every orphan be a vertex and every friendship be an edge. If the setup is $G$, let $K$ be the set of all maximal complete graphs in $G$; that is, a graph on $n$ vertices is in $K$ if and only if it is complete, and also not part of a complete $n+1$. Call everything in $K$ supercomplete. We claim that it suffices to show that each orphan is a member of at most $2$ supercomplete graphs. If this is true, then we can assign parents so that each supercomplete graph shares a single parent among itself, and any orphan in less than $2$ supercompletes can be given a new parent. Then obviously every pair of friends share a parent (because a friendship is a $K_2$) and no enemies can possibly share parents. Also the last condition is satisfied because any $K_3$ shares a single parent. So now we want to prove this. Suppose for the sake of contradiction that there exists an orphan $O$ which is included in $3$ distinct supercomplete graphs. Let the members of these graphs be $X_1,X_2,\dots ,X_a,Y_1,Y_2,\dots ,Y_b,Z_1,Z_2,\dots ,Z_c$ where $X_i$ are all members of a supercomplete, etc. (It's not immediately obvious that we should have $X_i\neq Y_j$ [to me anyway] but we don't assume this). Now we'll use our given. Consider $X_1,Y_1,Z_1$, at least one pair are friends, WLOG $X_1Y_1$. Then consider $X_1,Y_1,X_i$ for all $i$, we must have that $Y_1$ is part of the $X$ supercomplete. Now consider $X_i,Y_1,Y_j$ for all $i,j$. Then all the $Y_j$ are part of the $X$ supercomplete, so there is no $Y$ supercomplete, contradiction. We are done.

JBL wrote: Olympiad problems which take moderately complicated graph-theoretic situations and re-express them as very complicated word problems make me sad. On the other hand, this is a cute little problem, once the nonsense is stripped away. Well, the flavor-text is at least pretty funny Solution with Andrew He: of course, we consider the graph with vertices as children and edges as friendships. Consider all the maximal cliques in the graph (i.e. repeatedly remove maximal cliques until no edges remain; thus all edges are in some clique). Claim: Every vertex is in at most two maximal cliques. 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. $\blacksquare$ 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. 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 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 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!

Hopefully this is correct. Also, the wording here is quite unnecessary and it makes me sad MellowMelon wrote: 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, but no pair of enemies does, and no three parents are in a love triangle (where each pair of them has a child). Consider a graph with children as vertices and friendships as edges. Call a clique maximal if none of its supersets is a clique. Assign to each maximal clique a person acting as a parent for all the children in it. Henceforth, all cliques we refer to shall be maximal. Claim 1: No two cliques can have more than one vertex in common. (Proof) Suppose $u, v$ lie in two cliques $c_1, c_2$. Since both cliques are maximal, there exists $x_1 \in c_1$ and $x_2 \in c_2$ so that $x_1, x_2$ are enemies. Taking $\{u, v, x_1, x_2\}$ our condition is violated. $\square$ Claim 2: No vertex belongs to more than two cliques. (Proof) Suppose three cliques $c_1, c_2, c_3$ contain a common vertex $a$ and for $i \ne j$ let $u \in c_i$ and $v \in c_j$ be such that $u, v$ are enemies. Then, for any $x \in c_i$ (or $x \in c_j$), taking $\{a, u, v, x\}$ violates our condition, unless $x, v$ (or $x, u$), are enemies. So, we see that every pair $x, y$ with $x \in c_i$ and $y \in c_j$ is an enemy pair. Take $b, c, d$ from $c_1, c_2, c_3$ respectively, then $\{a, b, c, d\}$ violates the condition. $\square$ Finally, note that there can be no love triangles, since the corresponding three children will form a triangle, so they will have a common parent. To end our proof, assign all children with less than two parents random people who don't have relations with others. $\blacksquare$

Rather than turn away from the obnoxious wording and turn it into graphs, we will embrace the cringe. Define a gang of orphans to be a set of orphans who are all friends with each other, and such that there is no other orphan who is friends with all the gangsters (read: maximal clique). There are now two major claims which completely pin down the nature of the friendships in the orphanage. Claim 1: Each gang has at most two members in common. Proof of Claim 1: Suppose orphans $x$ and $y$ were in gangs $G$ and $H$. Then, suppose $a\in G$ and $b\in H$ with $a\not=x$ and $b\not=y$. Note that $y,a,b$ are all friends of $x$, yet $(a,b)$ is the only enemy pair, a contradiction, as desired. $\blacksquare$ Claim 2: Each orphan is in at most two gangs. Proof of Claim 2: Suppose orphan $x$ is in three gangs, so $x$ has three friends $a$, $b$, $c$, all of whom are in distinct gangs (this can be done by claim 1). Suppose $a$ and $b$ were friends, and let $A$ and $B$ be their respective gangs. Suppose $y$ and $z$ are members of $A$, then $a$ has friends $(b,y,z)$, and since $(y,z)$ are friends, we must have that $(b,y),(b,z)$ are friends. Therefore, $b$ is friends with all of $A$, contradicting the definition of a gang. Thus, $(a,b),(b,c),(c,a)$ are all enemies, again a contradiction, so each orphan is in at most two gangs. $\blacksquare$ Assign to each gang a Godfather, who will be one of the parents of each of the orphans in that gang. If an orphan is in two gangs, their parents will be the two Godfathers. To the orphans only in one gang, assign parents all at random, all distinct from one another and the Godfathers. This clearly has the property that friends share a parent (if two orphans are friends, we keep adding orphans till we get a gang, and the shared parent is the Godfather of that gang), and two enemies have no common parents (they must be in different gangs). Finally, there are no love triangles as then the three orphans must all be friends, so they are all in a gang, so they all share one parent, namely the Godfather of that gang.

Remark: Man this is a crazy orphanage. Sounds more like a warzone to me! Rather than embracing the cringe like @above does, I will use the graph theory interpretation like everyone else in this thread. First, spend $20$ minutes deciphering what this problem is trying to say. Consider a graph on $n$ vertices, where vertices represent orphans. Connect two vertices if the orphans they represent are friends. Consider all maximal complete graphs in $G$. Note that a maximal complete graph is a complete graph not part of a larger complete graph. It suffices to show that each vertex is part of at most two maximal complete graphs. We can assign each complete graph to some parent and then for the remaining children without friends, we just assign one parent to each. Furthermore, there cannot be a love triangle, since if $v_1, v_2$ share a parent and $v_2, v_3$ share another parent, by construction, $v_3, v_1$ cannot. Claim: No vertex is part of $\geq 3$ maximal compelte graphs. Proof: Let three cliques consist of orphans that we shall label \[K_A = \{A_1, A_2, \ldots , A_x\}\text{, } K_B = \{B_1, B_2, \ldots , B_y\}\text{, } K_C = \{C_1, C_2, \ldots , C_z\}.\]Consider $A_1B_1C_1$, in which some pair are friends. WLOG let this be $A_1B_1$. Then, comparing $A_1B_1A_i$ for all $i \in [2, x]$, we see that $B_1A_i$ must be friends so in fact $B_1 \in K_A$. So, if we look at $A_iB_1A_j$ for all valid pairs $(i, j)$, we see that $K_B \in K_A$, so $K_B$ doesn't exist, a contradiction. $\square$ And we are done! $\blacksquare$

Create a graph with orphans as vertices and friends as edges. The main idea is to examine cliques under the parents condition. Call a clique maximal if it is not a subset of a larger clique. Consider the (maximal) clique decomposition of a graph, which exists by removing a clique and inducting down. Suppose we have a clique $K_n$, and we need to assign each vertex in it parents. Consider an arbitrary vertex $v$, and say it has a parent $p$. Then, all other vertices in the clique must also have this parent $p$. We can assign each clique a parent. If we can show that each vertex is in at most 2 cliques in the clique decomposition of the graph, then we simply assign each vertex the parents of the 2 cliques it is a part of. If the vertex is only a part of one clique, assign its second parent as just a new different parent. This construction won't give any love triangles, since the resulting triangle would have its own parent. Claim: Any two cliques have at most 1 vertex in common. Proof: Suppose cliques $X,Y$ had two vertices $u,v$ in common. Since the cliques are maximal, there exists some vertices $x\in X, y\in Y$ such that $xy$ is not an edge. Then $u$ has 3 neighbors $v,x,y$, but only $vx,vy$ are edges, contradiction. $\blacksquare$ Claim: Any vertex is in at most 2 cliques. Proof: Suppose a vertex $v$ is in cliques $X,Y,Z$. Choose vertices $x\in X,y\in Y,z\in Z$, and WLOG $xy$ is an edge (at least one of $xy,yz,zx$ must be an edge). For all other $y'\in Y$, note that $v$ is adjacent to $x,y,y'$, and $xy,yy'$ are edges; hence $xy'$ is also an edge. So actually $x\in Y$, contradicting $Y$ being maximal. $\blacksquare$

Nothing new here, but posting for storage. Rephrase the problem in terms of a graph $G$ with vertices as kids, where we connect two kids iff they are friends. We assume henceforth that $G$ is connected (otherwise repeat the below on each connected component of $G$). Consider the set $S$ of all maximal cliques of $G$ (i.e. cliques for which no vertex not in the clique connects to each vertex in the clique). Note that each clique in $S$ has size at least $2$ (since $G$ is connected), that each vertex of $G$ is in at least one set in $S$, and that if $vw$ is an edge of $G$, there is a clique containing both $v$ and $w$. Claim 1: Let $s$ be an element of $S$, and $v \not\in s$ be a vertex of $G$ which is adjacent to a vertex in $s$. Then, $v$ is adjacent to exactly one vertex in $s$. Proof: Suppose not, and that $v$ connects to $u, w \in s$, and pick $r \in s$ which is not adjacent to $v$ (if such a vertex does not exist, then $v$ is adjacent to each element of $s$, contradicting the maximality of $s$). Consider the edges $uv, uw, ur$. Then, $vw, wr$ are edges, while $rv$ is not an edge. However, by the problem, an even number of $vw, wr, rv$ must be non-edges, contradiction. $\blacksquare$ We now claim that any two elements of $S$ intersect in at most one point. Indeed, let $s_1, s_2$ be elements of $S$, both of which contain $v \neq w$. Let $u$ be a vertex of $s_1$ which is not contained in $s_2$ (if such an element does not exist, we have $s_1 \subset s_2$, contradicting the fact that $s_1$ and $s_2$ are maximal cliques). Then, $u$ is adjacent to two vertices of $s_1$, contradicting Claim 1. Claim 2: Each vertex of $G$ is contained in at most $2$ elements of $S$. Proof: Suppose not. Let $v$ be a vertex of $G$ which is contained in three distinct elements of $S$, and let two of these be $s_1, s_2$. Let $w \not\in s_1 \cup s_2$ be a vertex of $G$ (which exists by our assumption). Let $v_1 \in s_1$, $v_2 \in s_2$, such that $v \not\in \{v_1, v_2\}$; since $s_1 \cup s_2 \supseteq v$, by the above we must have $s_1 \cup s_2 = v$, implying that $v_1 \neq v_2$. Since $w$ is not an element of either $s_1$ or $s_2$ and $w$ is adjacent to $v \in s_1 \cup s_2$, it follows by Claim 1 that $w$ is not adjacent to either $v_1$ or $v_2$. Similarly we find that $v_1$ and $v_2$ are not adjacent either. We have reached a contradiction as $v_1, v_2, w$ are all neighbors of $v$, yet none of the three pairs $v_1v_2, v_2w, wv_1$ are edges. $\blacksquare$ We are now ready to finish. In the sequel, we will construct an assignment of kids to parents. To each element $s_i \in G$ assign a parent $P_i$. For each kid in $s_i$, let them have parent $P_i$. For any kid who is part of two distinct cliques $s_i$ and $s_j$, they now have two parents $P_i$ and $P_j$. On the other hand, if a kid $v$ is part of only one clique $s_i$, we add an additional parent $Q_v$ whose only kid is $v$. This kid will then have parents $P_i$ and $Q_v$. We now demonstrate that this assignment satisfies the desired. For any two friends, there must be a clique containing them both; hence, they will share a parent. Meanwhile, for any two kids who are enemies, no clique contains them both, meaning that they cannot share a parent. Finally, we show that there is no love triangle. Indeed, suppose there exist distinct kids $u, v, w$ and parents $P_1, P_2, P_3$ such that $u$ has parents $P_2$ and $P_3$, $v$ has parents $P_3$ and $P_1$, and $w$ has parents $P_1$ and $P_3$. Since each pair $uv, vw, wu$ shares a parent, it follows that $uvw$ is a triangle, implying that there is an element $s_i \in S$ such that $s_i \supseteq \{u, v, w\}$. However, this implies that $P_i$ is a parent to each of $u, v, w$, contradicting the assumption that each of $P_1, P_2, P_3$ are distinct. We are done! $\Box$

bad write-up ahead Take the following graph interpretation: Let $G$ be a graph with the vertices as the orphans and the edges representing friendship. Furthermore, every group of $3$ orphans that have a common neighbor among them (other than the $3$ of them), then the number of edges that connect some of them is odd. Now, just assign 2 letters to each of the vertices which just represent the first letter of the names of the parents. Also, let $\{v_i\}$ denote the two letters assigned to the vertex $v_i.$ First, take all of the maximal cliques. Note that for all vertices that are part of clique will all have one common parent, and all other parents will be different. Lemma 1: A vertex in one maximal complete graph is adjacent to at most 1 other vertex in a maximal complete graph Proof. FTSOC assume there are at least two edges connecting the two maximal cliques. Let the vertices of the larger clique be $v_1, \dots, v_m$ and the vertices of the smaller maximal clique be $u_1, \dots, u_n.$ It is sufficient to prove that $u_i$ is adjacent to all of the vertices in the larger maximal clique, because then we would get a contradiction, since we get a larger clique. WLOG $\{v_1\} \cup \{v_2\} \cap \cdots \cap \{v_i\} = R$ and $\{v_1\} \cap \{v_2\} \cap \cdots \cap \{v_i\} = B.$ Now, let $u_i$ be adjacent to $v_i, v_j.$ Note that there must be an odd number of friendships between $u_i, v_j$ and another vertex in the larger maximal clique that is not adjacent to $u_i.$ But this is clearly false, a contradiction, the claim follows. Note that by Lemma 1, it follows that two cliques can only have at most 1 vertex in common. Lemma 2: Each vertex is at most part of two cliques Proof. Suppose the three cliques have a common vertex $a.$ Let the cliques have vertices $v_1, \dots, v_n$ and $u_1, \dots, u_m$ and $k_1, \dots, k_d.$ Let $a$ be adjacent to $u_i, v_k, k_d.$ Now, let any two of the cliques have some edge connecting any two vertices from each of the cliques. But by Lemma 1, this is impossible. Furthermore, if there are no edge connections between any of the cliques, $u_i, v_k, k_d$ don't satisfy the oddness condition in the problem. To finish, just note that there are no love triangles since there will be a common parent in a $K_3.$ Finally, for all edges in a clique, take the parent that is not common (among everyone) in the clique, and just make them a parent that no one else has. We are done! $\boxtimes$

Solution: Let each vertex represent an orphan and each edge represent two orphan friends. Consider a connected component. Claim 1: The union of $v$ and its neighbours form 2 cliques (one of them can be empty). Proof. Suppose $v$ connects to $n_1,\cdots,n_k$. Otherwise, WLOG, $n_1n_2$ is an edge. This implies $n_jn_1, n_jn_2$ are both edges, or both not edges. If they are both edges, they join the first clique. Let $S$ be the $n_i$'s not in the first clique. Taking two vertices in $S$ and $n_1$ imply $S$ is also a clique. This implies each vertex is part of two cliques. Start from an arbitary vertex, and give it parents $p_1p_2$. For the parents in the first clique, use $p_1$ and some other parent, and for the parents in the second clique, use $p_2$ and other parents. We can repeat the algorithm on other vertices because the above property exists. QED.

Rewrite the problem to evade trying to comprehend the wording as follows: Problem: (USA TSTST 2011/5) $G=(V,E)$ is a graph such that for each vertex $v$, if we choose three neighbors $u_1,u_2,u_3$ of $v$ then an odd number of choices of $i,j$ have $(u_i,u_j)$ an edge. Show that it is possible to assign the vertices pairs of colors so that any two neighboring vertices share exactly one color, no non-adjacent vertices share a color, and there are no three colors $c_1,c_2,c_3$ such that some vertex is labeled with both $c_i$ and $c_j$ for each choice of $i,j$. Note that it suffices to solve the problem for connected $G$, so from now on we assume $G$ is connected. Now, we analyze the set $N(v)$ and what the information gives about it. For now we work with the subgraph induced by $N(v)$. Let $w\in N(v)$ be arbitrary. Then $w$ partitions $N(v)$ into $A=N(v)\setminus\{u\}\cap N(w)$ and $B=N(v)\setminus\{u\}\setminus A$. The condition implies all elements in $A\cup \{w\}$ and all elements in $B$ have an edge between them, and there are no edges between $A\cup\{w\}$ and $B$, so $N(v)$ partitions into two (or one) cliques with no edges between each other. Now, we characterize $G$ itself. Consider a maximal clique $K_t$. Any vertex $v$ of that clique is either part of $1$ clique in which case all neighbors of $v$ are in $K_t$, or it is part of a second maximal clique $K_s$. Iterating this way gives us a network of maximal cliques $K_i$, any pair of which are connected by at most one vertex, and any vertex of which is part of at most two maximal cliques. These maximal cliques must include all vertices in $G$ because $G$ is connected. This essentially hands to us an easy way to assign the colors: assign each maximal clique a distinct color (don't worry about vertices having less than two colors, that can be accounted for later) and assign any vertex the colors of the maximal cliques it is in. This trivially satisfies the first condition and second condition. To see that it satisfies the third condition, note there otherwise intersect three maximal cliques intersecting at $u,v,w$, but considering maximal clique $uvw$ gives a contradiction: it shouldn't exist.

Similar to the above solutions. Consider the obvious graph theoretic interpretation. Let $v$ be a vertex and let $S = N(v)$. We know that for every triple of vertices in $S$, there's either $1$ or $3$ edges. Suppose $S$ is not a clique, then there are two vertices $x,y$ such that $xy$ is not an edge. So, By choosing $(x,y,z)$ for every other vertex $z$ in $S$, we have that everything else is connected to exactly one of $x,y$. Let $A$ be the set of things connected to $x$ and $B$ be the set of things connected to $y$. Let $p,q \in A$, then $(x,p,q)$ gives $pq$ is an edge, and therefore $A$ is a clique and similarly, so is $B$. $(x,a,b)$ for $a \in A, b \in B$ shows that there are no edges between $A,B$. So $N(v)$ is just one or two disjoint cliques for every vertex $v$. Pick the biggest clique in the original graph, put it in one set, among the remaining do it again, and keep repeating. This way, the graph is divided into a bunch of cliques. From the previous paragraphs, we see that any two cliques share at most $1$ vertex and also no three cliques share a vertex. To color, the vertices, give each clique a unique color and at each intersection give them another unique second color. For the second colors of the rest of the vertices, just assign something new. This works, so done. $\blacksquare$

Sussiest problem ever. Solved with i3435. We take the obvious graph-theoretic interpretation and assign a pair of numbers $\{x, y\}$, we refer to it as the astley pair. We consider the maximal clique decomposition of the graph and begin with the following claim, Claim: Two cliques cannot have more than $1$ vertex in common. Proof: FTSOC, suppose two cliques have two vertices $u$ and $v$ in common, WLOG, $\{1, 2\}$ and $\{1, 3\}$ have been assigned to them. Now, to avoid love triangles, all the vertices which form triangles with $u$ and $v$ must have $1$ in their astley pair. This forces every vertex of the cliques to be connected to each other which is clearly a contradiction. $\blacksquare$ Claim: A vertex is in atmost $2$ cliques. Proof: WLOG, let the astley pair of this pivot vertex be $\{1, 2\}$. First of all we take two cliques and fix their astley pairs to be of the form $\{1, i\}$ and $\{2, j\}$. Now, this forces all the vertices in the other cliques to be connected to either of these cliques which is again a contradiction. $\blacksquare$. For the construction, we first fix the astley pair of a vertex and then just assign one of the numbers in the astley pair of a vertex to one of the cliques and the other number in the second clique if they exist. $\blacksquare$

Induction is probably unnecessary here but it's easier to think about it this way (?) View the relationships as a graph, with an edge representing a friendship. We will induct on the number of vertices, with small $n$ being trivial. Suppose we add a vertex $v$ to the graph. Consider the set $S$ of all vertices that are connected to $v$ (i.e. friends with $v$). I claim that there exist two people $\{a,b\}$ such that any child in $S$ has either $a$ or $b$ as a parent. Essentially, this is saying that at most two (maximal) cliques exist in $S$. Indeed, if we had three maximal cliques $C_1,C_2,C_3$, then we could find $w_1 \in C_1$, $w_2 \in C_2$, and $w_3 \in C_3$ such that $w_1,w_2,w_3$ aren't adjacent, but this contradicts the fact that an even number of pairs of them are enemies. Given the existence of such a set $\{a,b\}$, set $a$ and $b$ to be the parents of $v$. Suppose some enemy $e$ of $v$ has parent $a$ as well. If no children in $S$ have parent $a$, then we're actually picking $a$ arbitrarily, so we just pick a different value of $a$. Now suppose at least one child in $S$ has parent $a$, and suppose its parents are $(a,c)$. If no enemy of $v$ has parent $c$, then pick $c$ instead of $a$. Otherwise, let $d$ be an enemy of $a$ with parent $c$. Considering the three friends $v,d,e$ of the child with parents $(a,c)$, we find that $d$ and $e$ must be friends, but then a love triangle exists in the orphanage formed by excluding $v$, which violates the inductive hypothesis. Thus no enemy of $v$ shares one of its parents. Finally, we must show that no love triangle exists involving $v$. Suppose we had two children with parents $(a,c)$ and $(b,c)$ (in $S$). If these were the only elements of $S$, then we could instead choose $v$'s parents to be $\{c,x\}$, with $x$ arbitrary. Otherwise, there would WLOG exist another friend of $v$ with parents $(a,d)$. But there is only one pair of these three friends who are enemies—$(b,c)$ and $(a,d)$—so this cannot occur. Combining these three facts completes the induction, so we're done. $\blacksquare$

Let $G$ be the graph with the vertices on the orphans and an edge representing friendship. Partition the edges of $G$ into maximal cliques greedily; the key is the following claim: Claim. Every vertex $v$ is in at most two such cliques. Proof. Suppose some vertex $v$ is in three. Then, for vertices $v_1, v_2, v_3$, each in one of the cliques, it follows that one pair $v_iv_j$ are friends, say $v_1v_2$, and let the clique at $v_2$ be larger. Now for some $u$ in the same clique as $v_2$, note that $uv$ and $v_2u$ are both edges, so it follows that $v_1u$ is an edge. This means that $v_1$ is part of the clique at $v_2$, which contradicts maximality. $\blacksquare$ So assign each clique a distinct parent. Now, suppose that there exists a love triangle; then, three cliques $K_1, K_2, K_3$ overlap in pairs at $v_1, v_2, v_3$ respectively. Let $u$ be any vertex in $K_3$; then, it follows that $uv_3$ is connected, so $v_3$ belongs in $K_3$ too, contradiction again.

Nice question

Gsolved with kotmhn and Om245. Let consider graph $G$. We consider every vertex as child or orphan and there is edge between two vertices if and only if they are friends. We call clique as gang. Claim: Neighborhood set of every child contain at max $2$ gang. Consider some baby child $C$. If it's connected to $A$ and $B$ such that there is edge between $AB$. Now if we have some kid $D$ which is friend of $C$ and atleast one of $A$ or $B$. Then note that for even number of enemies pairs, only possiblity is $DA$ and $DB$ both are edges. Consider set $R$ contains $A,B,D$. We consider all those vertex which are common friends with $C$ and common friend with some orphan in $R$. Observe by same argument it will also part of $R$ and all vertecies in $R$ connected to each other. If there are $3$ or more such gangs connected to $C$ then let $R_1,R_2$ and $R_3$ are $3$ of them. Then as there is no edge between these gangs consider $3$ vertex each from one gang and $C$. As there will be $3$ pair of lifelong enemies, this is not possible. Hence atmax $2$ gangs can be there. Claim: Two different gangs can have at max $1$ child common. If it have more then $1$, we consider $2$ common vertex in two gangs $A$ and $B$. Also consider $C$ and $D$ child each one from one gangs $C$ and $D$ who are enemies. Note this exists as otherwise they are not different gangs. Now from $A$ we have $B,C,D$ as friends. But there are only one pair of enemies between orphans, not fair. Now we do parenting of orphans. (Distributing $2$ parent to each child) Suppose take some teenager child, we assign mother and father to first child or $p_1$ and $p_2$ parents to it. Now as we have at most $2$ gangs, we will give $p_1$ to one gangs and $p_2$ to other if necessary. Now we do same parenting for each child, As if, some of friend of first child we have $p_1$ as it's parent already. Now we give some new parents $p_3$ to new friends (which are not of good friends of first child). Similarly each time we introduce new parents as we have infinite supply of parents. Then no parent will fall in love triangle.