Coloured matchings in bipartite graphs

A theorem of Stein (1975, 1979) states that for every n × n (n ⩾ 3) complete bipartite graph G such that every edge is coloured and each colour is the colour of at most two edges, there is a perfect matching whose edges have distinct colours. We give an O(n2) algorithm for finding such a perfect matching. We show that a related problem is NP-complete.