gistfile1.sql

with n as (
    select a.state_name a, b.state_name b
    from usa_state_shapefile a
       , usa_state_shapefile b
    where ST_Dimension(ST_Intersection(a.the_geom, b.the_geom)) > 0
)
select w.a w, x.a x, y.a y, z.a z
from n w
join n x on x.a = w.b
join n y on y.a = x.b
join n z on (z.a = y.b and z.b = w.a)
where not exists (select * from n where a = w.a and b = x.b)
and not exists (select * from n where a = x.a and b = y.b)
and w.a < x.a and w.a < y.a and w.a < z.a and x.a < z.a
;

That's beautiful. You could use ST_Relate to get a DE9IM pattern that shows 2-d boundary conditions and avoid the full intersection calculation.