MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2018/2019
A. 731
A. 731
Part of
KoMaL A Problems 2018/2019
Problems
(1)
Embed a graph on given points
Source: KöMaL A. 731
11/12/2018
Let
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
be a tree graph with
n
n
n
vertices, and let
P
P
P
be a set of
n
n
n
points in the plane with no three points collinear. Is it true that for any choice of graph
G
G
G
and set
P
P
P
, we can embed
G
G
G
in
P
P
P
, i.e., we can find a bijection
f
:
V
→
P
f:V\to P
f
:
V
→
P
such that when we draw line segment
[
f
(
x
)
,
f
(
y
)
]
[f(x),f(y)]
[
f
(
x
)
,
f
(
y
)]
for all
(
x
,
y
)
∈
E
(x,y)\in E
(
x
,
y
)
∈
E
, no two such segments intersect each other?
combinatorics