In a group of people, there are some mutually friendly pairs. For positive integer $k\ge3$ we say the group is $k$-great, if every (unordered) $k$-tuple of people from the group can be seated around a round table it the way that all pairs of neighbors are mutually friendly. (Since this was the 67th year of CZE/SVK MO,) show that if the group is 6-great, then it is 7-great as well. Bonus (not included in the competition): Determine all positive integers $k\ge3$ for which, if the group is $k$-great, then it is $(k+1)$-great as well.
Problem
Source: Czech and Slovak Olympiad 2018, National Round, Problem 1
Tags: combinatorics, graph theory, national olympiad
06.04.2018 00:11
Assume there is a group of people that is $6$-great but not $7$-great. As usual we consider a graph $G$ where the vertices represent the people and the edges represent the friedships. The group of people is $k$-great if for any choice of $k$ vertices of $G$ there exists a cycle containing these vertices. Now, we choose $7$ vertices of $G$ for which there exists no cycle containing all of them and take a closer look at the graph out of those vertices and all edges between them that are a part of $G$. Let $v$ be one of those vertices. Since the group is $6$-great there is a cycle which contains the remaining $6$ vertices. [asy][asy] draw((1,0) -- (0.5,0.86) -- (-0.5,0.86) -- (-1,0) -- (-0.5,-0.86) -- (0.5,-0.86) -- cycle); draw((0,0) -- (1,0), dashed); draw((0,0) -- (0.5,0.86), dashed); draw((0,0) -- (-0.5,0.86), dashed); draw((0,0) -- (-1,0), dashed); draw((0,0) -- (-0.5,-0.86), dashed); draw((0,0) -- (0.5,-0.86), dashed); dot((1,0), blue); dot((0.5,0.86), blue); dot((-0.5,0.86), blue); dot((-1,0), blue); dot((-0.5,-0.86), blue); dot((0.5,-0.86), blue); dot((0,0), red); label("$v$", (0,0), N); [/asy][/asy] If more than $3$ of the dashed edges are a part of $G$, then there are two neighbouring dashed edges and there is a cycle containing all $7$ vertices, which is a contradiction. Thus, $\deg v \leqslant 3$. Now, we look at a cycle containing $6$ vertices including $v$. Let $w$ be a neighbour of $v$ in this cycle. [asy][asy] draw((1,0) -- (0.5,0.86) -- (-0.5,0.86) -- (-1,0) -- (-0.5,-0.86) -- (0.5,-0.86) -- cycle); dot((1,0), red); label("$v$", (1,0), E); dot((0.5,0.86), blue); label("$w$", (0.5,0.86), NE); dot((-0.5,0.86), blue); dot((-1,0), blue); dot((-0.5,-0.86), blue); dot((0.5,-0.86), blue); dot((0,0), blue); [/asy][/asy] Obviously, we have $\deg v \geqslant 2$. But since there is also a cycle through the $6$ vertices excluding $w$, we can even conclude that $\deg v \geqslant 3$. Combining these two results we get $\deg v = 3$. Adding the degrees of the $7$ vertices we get $21$, which is a contradiction to the handshaking lemma. Therefore, there is no group of people that is $6$-great but not $7$-great.
01.05.2018 00:56
As above it suffices to prove for 7 vertices. It is easy to show each vertex has degree at least 3 and by parity one must have degree at least 4. If we look at this Vertex and the hexagon on the other 6 we can forma the desired 7-cycle.