Organize a tournament
Haskell: 291 chars

Another solution which terminate only if there is a solution without any collision (5 and 6). It is also very fast:

import System.Environment
import Data.List
a n=[(x,y)|x&lt;-[1..n],y&lt;-[1..n],x&lt;y]
s []=[[]]
s (m:[])=[[m]]
s ((x,y):(x',y'):xs )
 |(x==x')||(x==y')||(y==x')||(y==y')=s((x,y):xs++[(x',y')])
 |0&lt;1=[(x,y):ys|ys&lt;-s((x',y'):xs)]
main=do
 args &lt;- getArgs
 print $ head $ s $ a (read(head args)::Int)