The government wants to create a team with one alchemist, one builder, and one computer-scientist.
In order to have good cooperation, it is important that the 3 team-members like each other.
Therefore, the government gathers $k$ candidates of each profession, and creates their "liking" graph. This is a tri-partite graph, where there is an edge between $a$ and $b$ iff $a$ likes $b$.
(Note that the "like" relation is symmetric but not transitive, i.e.: if $a$ likes $b$ then $b$ likes $a$, but if $a$ likes $b$ and $b$ likes $c$, then not necessarily $a$ likes $c$).
Is this always possible to create a team? Of course not. For example, it is possible that no alchemist likes any builder.
However, suppose the "liking" graph has the following property: in each group of 3 alchemists and 3 builders, there is at least a single alchemist-builder pair that like each other; ditto for alchemists-computerists and builders-computerists.
Given this property, is this always possible to create a team where all 3 members like each other? If so, what is the minimum number of candidates of each type ($k$) that the government will have to gather?
I would like to both find k and prove that it is the minimum.
A possibly related sub-question is: in a group of $k$ alchemists and $k$ builders, what is the minimum number of pairs that like each other? For $k=3$, by the assumption of the question, that number is 1. What about $k>3$?
A third question is: what is the name of this kind of problems?