First,let us rewrite the problem statement in the language of graph theory: Problem: A graph $G$ has three parts $V_1,V_2,V_3$ each having $n$ vertices and for any $v \in V_i$ the degree of $v$ in each of $V_{i+1},V_{i+2}$ is at least $\frac{3n}{4}$.Prove that we can partition the vertices of $G$ into $n$ set of the for $(x_i,y_i,z_i)$ with $x_i \in V_1 ,y_i \in V_2 ,z_i \in V_3$ such that all these sets are triangles. We begin with a useful lemma: Lemma: In a bipartite graph $G=(V_1,E,V_2)$ with $|V_1|=|V_2|=n$ each vertex has degree at least $\frac{n}{2}$.Then there is a perfect vertex matching in $G$.(We can choose $n$ disjoint edges) Proof: We prove the lemma by contradiction.Due to the converse of Hall's Marriage theorem,there exists a set $A \subset V_1$ such that the set of vertices adjacent with at least one vertex in $A$ has less than $|A|$ vertices(call this set $B \subset V_2$).since each vertex in $V_1$ has degree at least $\frac{n}{2}$ so $|B| \geq \frac{n}{2} \implies |A| >\frac{n}{2}$.But this is impossible,since a vertex $v$ not in $B$ should be connected to at least on vertex in $A$. Back to main problem: Applying lemma to sets $V_1,V_2$ implies that there is a perfect matching between them.Let the edges of this matching be $e_1,\dots e_n$.Construct a graph $H$ with vertices denoting $e_i$ and draw and edge between $v \in V_3$ and $e_i \in H$ if and only if $v$ is connected to both of the vertices of $e_i$.It's Obvious that the condition of the lemma is satisfied for $H,V_3$,so by the lemma,we are done.

If the relation of "knowing another" was not mutual, can we find a bound on the number of teams of 3 where all 3 know each other? How about just disjoint directed 3-cycles? P.s. it is 2 am here and I am way too lazy to think now that's why I am asking so many -possibly silly- questions.

The problem follows from the following lemma. Lemma: Suppose we have a bipartite graph with $n$ vertices on each side and such that each degree is at least $n/2$. Then, this graph has a perfect matching. Proof: As expected, we simply verify Hall's condition. Let $X$ be any nonempty subset of the left set of vertices. Note that $N(X)\ge n/2$ just by virtue of any one vertex in $X$, so Hall's condition automatically holds if $|X|\le n/2$. We'll now restrict our attention to $|X|>n/2$. Surprisingly, it turns out that $N(X)$ is in fact the full right vertex set (which clearly implies Hall's condition). Indeed, suppose some vertex $y$ on the right was not in $N(X)$. Then, there is no edge from $X$ to $y$. But the degree of $y$ is at least $n/2$, and $|X|>n/2$, so $N^{-1}(\{y\})$ and $X$ have to intersect by pigeonhole or something, so we have a contradiction. This shows that $N(X)$ is the full right vertex set, so we're done by Hall's theorem. $\blacksquare$ Now, we see that there is a perfect matching between the students of say the first two classes by the lemma. Now construct a bipartite graph $G$ with the edges of the first matching as the $M$ vertices on the left, and the third class on the right. Draw an edge between original matching edge $ab$ and third class student $c$ if and only if $ac$ and $bc$ know each other. Suppose we have an original matching edge $ab$. We see that $a$ knows at least $\frac{3}{4}M$ of the third class, and so does $b$. Therefore, they both know at least $\frac{M}{2}$ of the third class by pigeonhole or something. Similarly, suppose we have a third class student $c$. She knows at least $3M/4$ students from each of the first two classes, so again by pigeonhole, $c$ is connected to at least $\frac{M}{2}$ of the original matching edges. Thus, $G$ has all degrees at least $M/2$, so by the lemma, $G$ has a perfect matching. By definition of $G$, this means that there are $M$ non-intersecting groups of $3$ students, one from each class, so we're done.

https://artofproblemsolving.com/community/c7h421528p2381669

Let $A, B, C$ be the classes and $G_c=(A+B, E_c)$ be a bipartite graph such that $ab\in E_c$ if $a$ and $b$ are friends. Similarly define $G_a, G_b$. Since any bipartite graph $n\times n$ with minimal degree $\geq\frac{n}{2}$ has a perfect matching, $G_c$ must have a perfect matching since it's minimal degree is $\geq\frac{3}{4}M\geq\frac{M}{2}$ and $\mid A\mid=\mid B \mid=M$. Let this perfect matching be $F= \{a_1b_1, a_2b_2,\dots,a_Mb_M\}$, where $\{a_1, a_2,\dots,a_M\}=A$ and $\{b_1,b_2,\dots,a_M\}=B$ Consider now the bipartite graph $G=(F+C,E)$ such that $a_ib_i\in F$ and $c_j\in C$ are adjacent if $c_ja_i\in C_b$ and $c_jb_i\in C_a$ (i.e. $c_j$ is a friend to both $a_i$ and $b_i$). It suffices to show that $G$ has a perfect matching. We will prove that the minimal degree of $G$ is $\geq\frac{M}{2}$. Indeed, $$\deg_G (a_ib_i)=\mid N_{G_a}(b_i)\cap N_{G_b}(a_i) \mid\overset{PIE}{=}\mid N_{G_a}(b_i)\mid+\mid N_{G_b}(a_i)\mid-\mid N_{G_a}(b_i)\cup N_{G_b}(a_i)\mid\geq\frac{3}{4}M+\frac{3}{4}M-M=\frac{M}{2}$$and $$\deg_G(c_j)=\mid N_{G_a}(c_j)\cap F(N_{G_b}(c_j))\mid\overset{PIE}{=}\mid N_{G_a}(c_j)\mid+\mid F(N_{G_b}(c_j))\mid-\mid N_{G_a}(c_j)\cup F(N_{G_b}(c_j))\mid\geq\frac{3}{4}M+\frac{3}{4}M-M=\frac{M}{2}$$Hence, we can label $C=\{ c_1,c_2,\dots,c_M \}$ such that $a_ib_ic_i \forall i\in{1,2,\dots,M}$ together form $M$ teams with 3 members who know both of their teammates.

This works right? Let $A$, $B$, and $C$ be the classes. By a well-known consequence of Hall's Marriage Theorem, there exists a perfect matching between $A$ and $B$, as each student in $A$ or $B$ knows at least $\tfrac{M}{2}$ students in the other class. Pair the students up according to this matching, and let $S$ be the set of student pairs. Then each student in $C$ knows at least $1-\tfrac{M}{4}-\tfrac{M}{4}=\tfrac{M}{2}$ pairs in $S$ (i.e. knows both students in the pair), and likewise each student pair in $S$ knows at least $1-\tfrac{M}{4}-\tfrac{M}{4}=\tfrac{M}{2}$ students in $C$ (i.e. is known by both students in the pair), so by the same \say{well-known consequence} there exists a perfect matching between $S$ and $C$, so we're done. $\blacksquare$

IMC 2011, Day 2, Problem 2

Consider the problem as a tripartite graph on the three senior classes $A$, $B$, and $C$, where two students from different classes are connected if they know each other. It suffices to show that we can find a set of $M$ disjoint triangles with one vertex from each class. By a corollary of Hall's theorem, as every vertex in $A$ has at least $\frac 34 M > \frac 12 M$ neighbors in $B$, there is a matching between $A$ and $B$, say between vertices $a_i$ and $b_i$ for $1 \leq i \leq M$. Now, as $a_i$ and $b_i$ both have at least $\frac 34 M$ neighbors in $C$, they have at least $\frac 12 M$ common neighbors in $C$. Color the edges between $b_i$ and its common neighbors in $C$ with $a_i$ red. Now consider any vertex $c \in C$. As $c$ has $\frac 32 M$ total neighbors within the union of $M$ sets $\bigcup_{i=1}^M \{a_i, b_i\}$, by Pigeonhole there are $\frac 12 M$ such sets where $c$ is neighbors with both $a_i$ and $b_i$. Then $c$ and $b_i$ are connected with a red edge for every such $i$. In particular, this means that every $b_i$ and $c_i$ have at least $\frac 12 M$ red edges. Now, we may construct a perfect matching between $B$ and $C$ using these red edges only, say between $b_i$ and $c_i$ for each $i$. Then by hypothesis, $\{a_i, b_i, c_i\}$ form a triangle for each $i$, which is our desired choice.

old sol. Let the students be sets $A$, $B$, $C$. Take a matching $B + C$ which exists by Hall's condition under knowing each other. Then, consider a bipartite graph between $A$ and $B + C$ with connections when $A$ knows both $B$ and $C$. Since each student in $A$ knows at least $\frac{3}{4}M$ students in both other classes, then there are at least $\frac{1}{2}M$ connections for each student in $A$. Likewise, there are at least $\frac{1}{2}M$ connections for each pair in $B + C$. Then, let $V$ be a subset of $A$. If $|V| \le \frac{1}{2}M$, the result holds trivially. Else, if $|V| > \frac{1}{2}M$, then every element of $B \times C$ is in $N_G(V)$ and Hall's condition follows.

Label the classes as $A$, $B$, and $C$. Pair the vertices of $B$ and $C$ and view those $M$ edges as vertices of a new bipartite graph, while the vertices of $A$ remain the same. In other words, create a new set of vertices $D$ out of $B$ and $C$, where each vertex $d_i$ in $D$ represents the edge between $b_i$ and $c_i$. Thus, we narrow our focus from a tripartite graph to a bipartite graph. The PIE argument, \[ \frac{3M}{4} + \frac{3M}{4} - |N_{AB}(b_i) \cap N_{AC}(c_i)| \leq M, \]shows that for every $i$, \[ \deg_{AD}(d_i) \geq \frac{M}{2}. \]A similar argument works for \[ \deg_{AD}(a_i) \geq \frac{M}{2} \]as well. These two facts are enough to show that those disjoint triangles exist.

Call the classes $A, B, C$. Note that there exists a perfect matching from $A$ to $B$ since the degree of each vertex in each class is greater than $\frac{M}{2}$. Call the pairs created from the perfect matching $(x_1, y_1), (x_2, y_2), \dots, (x_M, y_m)$. Let the students in class C be $z_1, z_2 \dots, z_M$.Note that $\deg(x_i) + \deg(y_i) - M \geq \frac{M}{2}$, so both students in a pair both know at least $\frac{M}{2}$ people. As for $z_1$, observe that it can not know at most $\frac{M}{2}$ people, so it must completely know at least $\frac{M}{2}$ pairs. Therefore, there exists a perfect matching from these pairs to the vertices in $Z$, which is what we want, so we're done.