Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts: 

1) we construct a graph that allows large online matchings (main part) 
2) we use this graph to prove the theorem

The question about online matching could be interesting in itself.