MathDB

Each vertex

v

and each edge

e

of a graph

G

are assigned numbers

f(v)\in\{1,2\}

and

f(e)\in\{1,2,3\}

, respectively. Let

S(v)

be the sum of numbers assigned to the edges incident to

v

plus the number

f(v)

. We say that an assignment

f

is cool if

S(u) \ne S(v)

for every pair

(u,v)

of adjacent (i.e. connected by an edge) vertices in

G

. Prove that for every graph there exists a cool assignment.

Problem Statement