At this year's Olympiad, some of the students are friends (friendship is symmetric), however there are also students which are not friends. No matter how the students are partitioned in two contest halls, there are always two friends in different halls. Let $A$ be a fixed student. Show that there exist students $B$ and $C$ such that there are exactly two friendships in the group $\{ A,B,C \}$. Proposed by Mirko Petrushevski
Problem
Source: 2021 Junior Macedonian Mathematical Olympiad P1
Tags: graph theory, combinatorics
08.06.2021 19:59
Take the obvious graph interpretation. Assume that for some fixed vertex $A$, for every other vertex $B,C$, there are $3,1$ or $0$ edges among them. However if the graph wasn't connected, then we could partition it joining some connected components and contradicting the problems condition, so graph is connected and $0$ is not an option. Take any neighbor of $A$ and call it $B$. So for every other neighbor of $A$, $B$ has to connected with it, and so neighbors of $A$ make a complete graph(including $A$). Let $C$ be a vertex not neighbor of $A$. By our assumption, $C$ cannot be connected to this complete graph. Also for every vertex $B$ connected to $A$, all of its neighbors must be connected to $A$. So this complete graph is isolated, contradicting the connectivity.
08.06.2021 21:54
Elementary: interpret the relationships as a graph. Now choose one of the groups to be the vertex $A$ and another to be all the other vertices, then say $A$ has degree $k>0$(this follows from the problem statement). Now let $S$ be the set of all the friends of $A$. If there are $B^{'}$ and $C^{'}$ in $S$, which are not friends, then the problem is solved, so $S\cup A$ is a clique. Now divide all the students into $S\cup A$ and all the rest (this is a group of at least one student, otherwise the graph is itself a clique, a contradiction by the problem statement). Therefore there is $B_{1}\in S$ and a student $C_{1}\not\in S\cup A$, such that $B_{1}$ and $C_{1}$ are friends. We chose $S$ as all the players of $A$, so $A$ and $C_{1}$ are not friends, so $\{A,B_{1},C_{1}\}$ have exactly two friendships.
09.06.2021 00:45
The corresponding friendship graph $G$ is connected. Let $u_1$ and $u_2$ be non-adjacent vertices. Let $P_i$ be a path from $A$ to $u_i$ (in the case $A=u_j$ for some $j$, ignore about $P_j$). Let $v_i$ be the vertex on $P_i$ adjacent to $A$ and closest to $u_i$. In case of $v_i = u_i$ for $i=1,2$, we are done. So, WLOG, let's say $v_1\ne u_1$. Then, we are done by taking $B=v_1$ and $C$ to be the person on $P_1$ adjacent to $v_1$ that is closer to $u_1$.
09.06.2021 09:24
Students be vertices in graph $G$. Draw an edge between $2$ vertices when students are friend in respective vertices. If $G$ isn't connected, then divide it into connected components and divide these components into 2 groups and we will get contradiction from satatesment. Then $G$ is connected , but not complete graph, because there exist at least 2 students which aren't friend. Since $G$ is connected take any $2$ vertices $A_{i} ,A_{j}$ which aren't neighbour and draw a path from $A_{i}$ to $A_{j}$ with $min$ degree ( path is in form of $A_{i} - A_{i+1} - ...-A_{j-1} -A_{j}$) . For shake contradiction assume there isn't $3$ vertices holds statesment. Then we will find that $A_{i}$ and $A_{i+2}$ are neighbour which makes contradiction with minimality of degree of path. It means that $\forall$ $2$ vertices are neighbour which means $G$ is complete. Again contradiction $\blacksquare$