#Haskell, 409

not fully golfed yet.

import Data.List r((c,h):s)|l<-r s,(x,y)<-partition(\s->any(`elem`s)[c,h])l=nub(c:h:concat x):y r _=[] k s d|l<-sort$nub s=r[(x,y)|x<-l,y<-l,notElem(x,y)d,notElem(y,x)d,x/=y] m a b c|elem c[a,b]=c|0<1=' ' e s d=[nub[map(m x y)s|x<-g,y<-g,notElem(x,y)d,notElem(y,x)d,x/=y]|g<-k s d] q a b=and$zipWith(\a b->or[n a==n[drop i s++take i s|s<-b]|i<-[0..length$a!!0]])a b f a b d=q(e a d)(e b d) n=map$filter(/=' ') 

this works on all the test cases.

Haskell, 409

not fully golfed yet.

import Data.List r((c,h):s)|l<-r s,(x,y)<-partition(\s->any(`elem`s)[c,h])l=nub(c:h:concat x):y r _=[] k s d|l<-sort$nub s=r[(x,y)|x<-l,y<-l,notElem(x,y)d,notElem(y,x)d,x/=y] m a b c|elem c[a,b]=c|0<1=' ' e s d=[nub[map(m x y)s|x<-g,y<-g,notElem(x,y)d,notElem(y,x)d,x/=y]|g<-k s d] q a b=and$zipWith(\a b->or[n a==n[drop i s++take i s|s<-b]|i<-[0..length$a!!0]])a b f a b d=q(e a d)(e b d) n=map$filter(/=' ') 

this works on all the test cases.