6

Part of 2012 239 Open Mathematical Olympiad

Problems(2)

Stroll on the graph

Source: 239 2012 J6

G

be a planar graph all of whose vertices are of degree

4

. Vasya and Petya walk along its edges. The first time each of them goes as he pleases, and then each of them goes straight (from the three roads they have to choose the middle one). As the result, each vertex was visited by exactly one of them and exactly once. Prove that this graph has an even number of vertices.

Subsets not appearing in the row

Source: 239 2012 S6

n

S

, several subsets

A_1, A_2, \ldots , A_k

are distinguished, each consists of at least two, but not all elements of

S

. What is the largest

k

that it’s possible to write down the elements of

S

in a row in the order such that we don’t find all of the element of an

A_i

set in the consecutive elements of the row?