MathDB
Problems
Contests
Undergraduate contests
Putnam
1965 Putnam
B5
B5
Part of
1965 Putnam
Problems
(1)
Putnam 1965 B5
Source:
9/28/2020
Consider collections of unordered pairs of
V
V
V
different objects
a
a
a
,
b
b
b
,
c
c
c
,
…
\ldots
…
,
k
k
k
. Three pairs such as
a
b
ab
ab
,
b
c
bc
b
c
,
a
b
ab
ab
are said to form a triangle. Prove that, if
4
E
≤
V
2
4E\leq V^2
4
E
≤
V
2
, it is possible to choose
E
E
E
pairs so that no triangle is formed.
Putnam