MathDB
Problems
Contests
National and Regional Contests
Russia Contests
All-Russian Olympiad
1990 All Soviet Union Mathematical Olympiad
525
525
Part of
1990 All Soviet Union Mathematical Olympiad
Problems
(1)
ASU 525 All Soviet Union MO 1990 graph, n points, n(n-1)/2 edges, coloring
Source:
8/14/2019
A graph has
n
n
n
points and
n
(
n
−
1
)
2
\frac{n(n-1)}{2}
2
n
(
n
−
1
)
edges. Each edge is colored with one of
k
k
k
colors so that there are no closed monochrome paths. What is the largest possible value of
n
n
n
(given
k
k
k
)?
graph
Coloring
combinatorics