Several Math Olympiad Problems

Involving Graphs
A. Slinko

Note. All acquaintances, friendships and flights are two-sided. For ex-
ample, if A knows B, then B knows A.
1. Questions
1. (England,72) On a set S the relation “→” is defined so that
(a) For an arbitrary pair a, b ∈ S exactly one of the two a → b or
b → a is true;
(b) For arbitrary three elements a, b, c ∈ S a → b and b → c imply
c → a. Determine the maximal posssible number of elements of S.
2. (USA, 82) In a society consisting of 1982 people it is possible to choose,
out of every four persons, at least one who is acquainted with the other
three. What is the minimal number of persons who are acquainted with
everybody in this society.
3. (a) (England, 80) There are 10 people in a room and between each
three there exist two who are acquainted. Prove that there exist
four people who all know each other.
(b) (Poland, 77) Will the same statement be true for 9 people?
4. (Yugoslavia, 75) In a society every two persons who are acquainted do
not have common acquaintances, and every two persons who are not
acquainted have exactly two common acquaintances. Prove that in this
society all people have equal number of acquaintances.
5. (a) Is it possible for a knight to travel round an 8 × 8 chessboard in
such a way that every possible move or its reverse occurs exactly
once?

1
 (b) Answer this question also for a king, and for a rook.
6. (Hungary, 77) In each of three schools there are n students. Every
student knows in total n + 1 students from two other schools. Prove
that there exist three students from different schools who know each
other.
7. (Austria, 73) 2n different points A1 , . . . , A2n are given in a space (n >
1), and no three of them are lying on the same straight line. Let M
be a set consisting from n2 + 1 segments which ends are some of the
given points. Prove that there exists a triangle which vertices are given
points and all three sides belong to M . Show that for n2 segments such
a triangle may not exist.
8. (Romania, 78) Several boys and girls are having a party. It appeared
that for every group of boys attending the party the number of girls
acquainted with at least one of the boys from the group is not less than
the number of boys in this group. Prove that all boys can simultane-
ously dance, each with the a girl whom he knows.
9. (IMO, 92) Given nine points in space, no four of which are coplanar.
Find the minimal natural number n, such that for any colouring with
red or blue of n edges drawn between these nine points there always
exists a triangle having all edges of the same colour.
10. (IMO, Longlist 83) Ten airlines serve a total of 1983 cities. There is a
direct service (without a stopover) between any two cities. Prove that
at least one of the airlines provides a round trip with an odd number
of landings.
11. Seven points in the plane, no three of which are on the same line, are
joined in pairs by either blue or a red straight segment. Calling a
triangle chromatic if its vertices are among the given seven points and
its three sides are of the same color, show that there must be at least
four chromatic triangles.
12. A graph G is said to be k-edge-colourable if each of its edges can
be assigned one of k given colours in such a way that no edges with
a common vertex have the same colour, and then χe (G), the edge-
chromatic number of G, is the smallest k for which G is k-edge-
colourable.

2
 Show that the edge chromatic number of the complete graph Kn on n
vertices is given by


n − 1 if n is even
χe (Kn ) =
n if n is odd.

13. (IMO 97) An n × n matrix with entries from {1, 2, . . . , 2n−1} is called
a silver matrix if for each i the union of the ith row and the ith column
contains 2n−1 distinct entries. Show that:

(a) There exist no silver matrices for n = 1997;

(b) Silver matrices exist for infinitely many values of n.

Solutions
1. Suppose that S contains three elements a, b, c such that a → b and
a → c. Then we cannot have neither b → c which together with a → b
implies c → a nor c → b which together with a → c implies b → a. Thus
this situation is impossible. Similarly we prove that S cannot contain
three elements a, b, c such that b → a and c → a. It is clear now that
S cannot contain more than 3 elements. If four elements existed, then
for every a in S we would have either two arrows originated from a
or two arrows which terminate at a and we would have either first or
the second situations considered above. An example of a set S with 3
elements a, b, c can be constructed as follows: a → b, b → c, c → a.

2. If everybody knows everybody then the number is equal to 1982. Sup-

pose that we have a pair of people A and B who do not know each
other. Then for an arbitrary other pair C and D of people, different
from the previous two, they will know each other because, otherwise,
in the group A, B, C, D nobody will know the other three. If A and B
know everybody each, then the number is 1980. Suppose now that A is
not acquainted with B and also with C. Then any third person D must
know A, B, C, otherwise in the group A, B, C, D nobody will know the
other three, and hence everybody. Therefore the minimal number of
persons who are acquainted with everybody is 1979.

3
3. (a) Suppose the contrary that among any four people we have two
who are not acquainted. Then every person, say A, cannot have
more than 3 persons with whom she is not acquainted. Indeed,
if there were four such persons P, Q, R, S, then two of them, say
P and Q are not acquainted and we have a triple A, P, Q with no
two of them being acquainted. Therefore A has at least 6 people
B1 , B2 , B3 , B4 ,B5 , B6 with whom she is acquainted.
We will now repeat the same argument again for the group B1 ,
B2 , B3 , B4 ,B5 , B6 of six. We will prove that B1 cannot have
more than two people among this group with whom she is not ac-
quainted. Indeed, if she did not know three persons, say B2 , B3 , B4 ,
then two of them, say B2 and B3 , will not be acquainted and in the
group B1 , B2 , B3 no two persons are acquainted. Thus B1 knows
at least three among the group B1 , B2 , B3 , B4 ,B5 , B6 and we
denote them as C1 , C2 , C3 . Now if some two persons in this group
of four, say C1 and C2 , know each other, then among four people
A, B1 , C1 , C2 everybody knows everybody, the contradiction.
(b) The statement is still true. If there exists a person who knows 6
other persons, then we can argue as in (a). If everybody knows
exactly 5 others, then we have 9×5
2
pairs of people who know each
other which is impossible since this number is not an integer. Fi-
nally if someone is not acquainted with four people D1 , D2 , D3 ,
D4 , then every pair in this group of four must know each other.

4. Let us prove first that any two persons who are acquainted have equal
number of acquaintances. Suppose that A and B are acquainted and
A1 , A2 , . . . , An are all acquaintances of A, different from B. Then ac-
cording to the condition of this problem nobody knows each other
among B, A1 , A2 , . . . , An . Let us consider Ai . She is not acquainted
with B, therefore Ai and B have exactly two common acquaintances.
One of them is of course A, the second we will denote by Bi . Since
Ai and Aj do not have common acquaintances, we know that Bi is
different from Bj for i = j. Therefore we have a one-to-one mapping
Ai → Bi . Putting A in correspondence to B, we obtain a one-to-one
mapping from the set of acquaintances of A into the set of acquain-
tances of B, and we can deduce that A has no less acquaintances than
B. But similarly we can prove that B has no less acquaintances than A.

4
5. An Euler path in a connected graph G is a path which includes every
edge of G exactly once. The necessary and sufficient condition for
existence of such a path is that the graph has at most two vertices of
odd degree. We will use this.
For each of the three figures we take the squares of the board as the
vertices of a graph and join two vertices by an edge if the figure can
travel from one square to another in one move.

(a) In case of the knight we find eight vertices of odd degree, a2, a7,
b1, b8, g1, g8, h2, h7. So, the answer is ”No.”
(b) The answer is also negative for a king as the four corners are
of degree three. But for a rook the answer is positive since the
respective graph is regular with all vertices of degree 14. In this
case even Euler circuit exists.

6. Among all 3n students we choose one with the maximal number of

friends k in some other school. We call her A and assume that she is
from the first school and that she knows k students from the second
school. Than A knows exactly n + 1 − k students from the third school.
Note that this number is not zero since n + 1 − k ≥ n + 1 − n = 1.
Suppose that A knows B from the third school. Let us look at this
student more closely. If she knows one of the acquaintances of A in
the second school, say C, then A, B, C is a triple of students sought
for. If she does not, then she knows in the second school at most n − k
students and therefore she knows at least (n + 1) − (n − k) = k + 1
students in the first school. This is impossible because k was maximal.

7. Let us prove by induction that if in some graph with 2n vertices no

three edges form a triangle, then the number of edges does not exceed
n2 . This is certainly the case for n = 1 as the number of edges is never
greater than 1 = n2 .
Suppose that the statement is true for some n, let us prove it for the
number n + 1. Consider a graph with 2(n + 1) vertices such that no
three edges of it form a triangle. Choose any two vertices A and B
connected by an edge (The statement is trivial if such a pair cannot be
found.) Then each of the 2n vertices, which are not selected, cannot be
connected by an edge with both A and B. Therefore we have no more
than 2n + 1 edge with participation of A and B. The rest 2n vertices

5
 are connected by no more than n2 edges by the induction hypothesis.
In total we have no more than n2 + 2n + 1 = (n + 1)2 edges.
The example can be constructed as follows. Let us divide 2n vertices
into two equinumerous sets containing n vertices each. Let us connect
by an edge any two vertices belonging to different groups. We obtained
a graph with exactly 2n vertices. It does not contain triangles since
out of arbitrary three vertices two will belong to the same group and
will not be connected.

8. We will prove this by induction on the number of boys n. For n = 1 the

statement is trivial since for one boy there will be always a girl with
whom he is acquainted. Let us assume that the statement is true for
the number of boys less than n and suppose that we have now n boys.
Let us consider two cases.

(a) Assume that there is a group G of k < n boys such that the
total number of girls whom they know is exactly k. Then by the
induction hypothesis each of them can dance with a girl whom he
knows. For the rest boys and girls the condition of the problem will
be again fulfilled. Indeed, having a group H of m boys, nobody of
whom belongs to G, we can form a union G ∪ H of the two groups.
We will have at least k + m girls acquainted with somebody from
this larger group. Since no more than k girls know boys from G
we get at least m girls who know boys from H. Again we use the
induction hypothesis to find dancing partners for boys from H.
(b) In this case we assume that for every group G of k boys there exist
more than k girls who know boys from this group. In this case we
can choose one boy and give him as a partner any girl whom he
knows (there is at least one!), remove this pair from consideration
and it is clear that for the remaining group the condition of the
problem will be fulfilled. Applying the induction hypothesis for
this group we prove the result.

9. Any n points, with every two of them connected by an edge, we call a

complete graph on n vertices and denote Gn . An arbitrary graph on
n vertices is obtained by removing some edges of Gn . It is known that
if the edges of the complete graph G6 are coloured in 2 colours, then
there exist three edges in it, which form a monochromatic triangle. If

6
the reader is not familiar with this olympiad folklore, it is time to stop
reading and to solve this problem as a warm-up exercise.
The complete graph G9 on n vertices has 9×8
2
= 36 edges. Suppose that
33 of them are coloured in blue or red. Then only three edges will be
uncoloured, and we can choose three vertices which are the endpoints
of the first, the second and the third uncoloured edges, respectively.
If we remove these three vertices together with the edges connecting
them to the other points, we obtain a complete two-coloured graph on
6 vertices, which as we know contains a monochromatic triangle.
We will prove now that this value n = 33 is minimal value with this
property. We will construct an example of a two-coloured graph on 9
vertices with 32 edges and without monochromatic triangles.
We start with the complete graph G5 on 5 vertices coloured as shown
on Figure 1

where solid and dashed segments represent red and blue segments re-
spectively. By inspection we see that it does not contain monochro-
matic triangles. Now we will describe a construction which being ap-
plied to a two-coloured graph Hn on n vertices without monochromatic
triangles, and with a vertex A which connected with all other vertices,
gives a two-coloured graph Hn+1 on n + 1 vertices which also has no
monochromatic triangles.
We add to Hn a new vertex N . We join N by edges with all vertices
of H except A and for an arbitrary vertex X of H we colour the new
edge N X exactly as AX was coloured (See Figure 2).

7
 Y

X
N

Note that no new monochromatic triangles appear. For example, N XY

cannot be monochromatic because AXY was not.
We apply this construction 4 times starting from H5 = G5 :

G5 −→ H6 −→ H7 −→ H8 −→ H9 .

The graph H6 will be the complete graph G6 with one edge deleted,
H7 will be G7 with two edges deleted, H8 will be G8 with three edges
deleted, and, finally, H9 will be G9 with four edges deleted. Note that at
each step of this construction we can choose a vertex which is connected
with all other vertices. Thus H9 is a two-coloured graph on 9 vertices
with 32 edges and without monochromatic triangles. It is shown on
Figure 3.

8
10. We may assume that exactly one airline does each direct service. If not,
then we cancel some of the flights which duplicate each other and still
be able to find a round trip with odd number of landings. The situation
can be modelled as an edge colouring of the complete graph on 1983
vertices with 10 colours. Given such a colouring we can consider 10
monochromatic graphs on these 1983 vetices be choosing the edges of
one of the 10 colours. Proving this theorem by contradiction we assume
that there are no monochromatic cycles of odd length.
Let us consider one of such monochromatic graphs, say the one coloured
with the tenth colour. Then we will prove that this graph is bipartite,
i.e. that the set of vertices can be split into two disjoint nonempty
subsets such that there is no edge drawn between any two vertices of
any of the subsets. To do this I choose one vertex A and label it with
a 0. All vertices immediately adjacent to it I will label 1. All vertices
adjacent to the vertices with a label 1 I will label with a zero and so on.
It remains to note that no one vertex will get both labels. Indeed, if a
vertex gets label 0, then there is a path from A of even length and if a
vertex gets label 1, then there is a path from A of odd length. There
cannot be both since otherwise we would have a cycle of odd length
originated from A. It is possible that not all vertices get labels because
they are not connected to A. The we choose an arbitrary such point
B, give it label 0 and continue the process of assigning labels until all
vertices get them. Then we collect all vertices with the label 0 in one
subset and all vertices with the label 1 in the other. By the construction
there are no edges between vertices labelled 0 and, similarly, no edges
between vertices labelled 1. At least one of the subsets contains 992
vertices.
From the previous paragraph we see that we can choose 992 vertices
such that all edges between them are coloured in one of the nine colours
1,2,...9. The same argument shows that there exist 496 vertices such
that all edges between them are coloured in one of the nine colours
1,2,...8, and continue this process further we will eventually get four
points such that all edges between them are coloured in just one first
colour. This is impossible since we can find a monochromatic triangle.
This contradiction proves the statement.

11. We split the proof into two lemmas. We say that the blue degree of a

9
vertex is d if it is a terminal point for exactly d blue segments. The
red degree is defined similarly.

Lemma 1. Suppose that a certain vertex has one of its degrees (blue or
red) greater than or equal to four. Then there are at least two chromatic
triangles with the same vertex.

Proof. Suppose that the segments AB, AC, AD, AE are blue. Then
consider the quadrilateral BCDE. It has four sides BC, CD, DE, EB
and two diagonals BD, CE. If among these six segments two or more
are blue, we have two chromatic blue triangles with a common vertex
at A. If not, then at most one of these six segments is blue, say BC
and the remaining five are red. Then the triangles BDE and CDE wil
be chromatic red triangles with a common vertex at C (or D).

Lemma 2. Among any six points there exist at least two chromatic
triangles.

Proof. By Lemma 1 we may assume that all red and blue degrees are
either 2 or 3. Let p2 be the number of vertices with blue degree 2 and
p3 be the number of vertices with blue degree 3. Let also L be the
number of blue segments. The total number of segments is 15 and we
may assume that we have more blue segments than red ones. Hence
L ≥ 8. On the other hand, since all blue degrees do not exceed 3, we
get 2L ≤ 18, whence L ≤ 9.
Each of the L blue segments participates in 4L triangles, where those
with two blue segments are counted twice and those with three blue
edges are counted thrice. Also the two blue edges that terminate at any
vertex of blue degree 2 form one triangle with 2 or three blue segments
in it and the three blue segments that terminate at any vertex of blue
degree 3 form 3 such triangles. Hence p2 + 3p3 gives us the number of
triangles with two or three blue edges, where blue chromatic triangles
are counted three times while those with two blue edges and one red
edge are counted only once. Hence S = 4L − p2 − 3p3 is the number of
triangles with one or two blue edges. Since

p 2 + p3 = 6
2p2 + 3p3 = 2L

10
 we get p3 = 2L − 12 and S = 4L − 6 − 2p3 = 18. Since the total number
of triangles is 6·5·4
6
= 20, we always have two chromatic triangles.

Proof. It is easy now to prove the main statement. Assuming that all
vertices have their blue and red degrees equal to three immediately
leads to a contradiction since 7 · 3 = 21 is not divisible by two and
this must be the total number of segments. Thus at least one vertex
has one of its degrees equal to four, which by Lemma 1 leads to the
existence of two chromatic triangles with a common vertex. Removing
this vertex, we are left with 6 vertices among which we can find two
more chromatic triangles by Lemma 2. This proves the statement.

12. First, as the total number of edges of Kn is 12 n(n − 1) and the number
of edges of any one colour in a proper edge-colouring of Kn is at most
[ n2 ], so it follows that χe (Kn ) ≥ n − 1 if n is even, while χe (Kn ) ≥ n if
n is odd. On the other hand:

(a) If n is odd, then the edges of Kn can be n-coloured by making

the vertices the vertices of a regular n-gon, assigning each edge on
the boundary of this n-gon a different colour, and colouring every
edge in the interior the same colour as the (unique) boundary edge
parallel to it. (If the boundary vertices are labelled 1, 2, . . . n in
order, then the edge {x, x + 1} is coloured the same as the edges
{x − 1, x + 2}, {x − 2, x + 3}, and so on.)
(b) If n is even, note that Kn may be viewed as a copy of Kn−1 with
all its vertices joined to an nth vertex. If the edges of Kn−1 are
(n − 1)-coloured using the procedure outlined in part (a), there
will be a different colour missing at each vertex of Kn−1 . The
corresponding edges incident to the nth vertex may be coloured
with these, completing an (n − 1)-colouring of the edges of Kn .

13. This problem was not considered originally as a graph problem but
after some time it was clear for everybody. First we give the solution
which is close to official and then show that it can be obtained as a
consequence of the previous problem.
Solution 1 Solution: (a) Let n>1 be an integer. Suppose that a silver
n × n matrix A exists. Let x be a fixed element of {1, 2, . . . , 2n−1}
which does not appear on the diagonal of A. (Such an element exists,

11
since there are only n elements on the diagonal but 2n−1 elements in
total.) The union of the ith row and the ith column we shall call the
ith cross. The element x appears in each cross exactly once. If x is the
(i, j)th entry of A, then it belongs to the ith cross and also to the jth
cross. In this case we say that these crosses are x-linked. (For example,
in the matrix A below the 1st and the 4th crosses are 6-linked.) This
implies that all n crosses are partitioned into pairs of x-linked ones,
and therefore n is even. But 1997 is an odd number.
(b) For n = 2
 
1 2
A=
3 1

is a silver matrix. For n = 4 we have already several of them, for

example
   
1 2 5 6 1 2 4 5
 3 1 7 5   3 1 6 7 
A=  4 6
, B= .
1 2   7 5 1 3 
7 4 3 1 6 4 2 1

The construction of A can be generalized. Suppose that an n × n silver

matrix A exists. Then an 2n × 2n silver matrix D can be constructed
as follows:
 
A B
D= ,
C A

where B is the n × n matrix obtained from A by adding 2n to each

entry, and C is the matrix obtained from B by replacing all its diagonal
entries by 2n. This matrix will be again a silver matrix. To prove this
let us consider the ith cross of D. Suppose that i ≤ n; the other case
is similar. This cross is composed of the ith cross of A, the ith row
of B and the ith column of C. The ith cross of A contains numbers
{1, 2, . . . , 2n−1}. The ith row of B and the ith column of C together
contain the numbers {2n, 2n + 1, . . . , 4n−1}.
Solution 2: (b) We will prove that a silver n × n matrix exists for
any even n. We will consider a special class of silver n × n matrices
where all diagonal elements are equal to 2n − 1. Then this matrix can

12
be interpreted as a schedule for a round robin tournament, where each
team plays every other teams twice: once at home and once on the
field of the other team. Indeed, there must be n(n − 1) games, played
during 2(n − 1) = 2n − 2 days. So we might think that if a number k is
on the intersection of the ith row and jth column of the silver matrix,
this means that the ith team plays the jth team at home on the kth
day of the tournament. It is also clear that such a tournament will give
us a silver matrix.
Now let us construct an n × n silver matrix. Let us consider a complete
directed graph on n vertices. We might think of a complete graph,
−
→ −
→
where each edge ij is replaced with two arrows ij and ji . According
to the previous problem, this graph must be 2(n − 1)-edge-colourable.
−
→
Now we translate this into a matrix as follows: if the edge ij is coloured
with the kth colour, we put k in the ith row and jth column of the
matrix. It is easy to check that we obtain a silver matrix.

13