Create a grouping based on chains of pairs
That's a complicated puzzle.  I've found a solution that starts with a list of all identifiers.  Then for each identifier, it creates an array of identifiers that it is paired with.  It iteratively expands that array (called "members") until all pairs are included.

; with  recursive list as
        (
        select  id1 as id
        from    pairs
        union
        select  id2
        from    pairs
        )
,       cte as
        (
        select  id
        ,       ARRAY[id] as members
        from    list
        union all
        select  cte.id
        ,       members || ARRAY[p.id1, p.id2]
        from    cte
        join    pairs p
        on      (
                    cte.members @&gt; ARRAY[p.id1] 
                    and not cte.members @&gt; ARRAY[p.id2]
                )
                or
                (
                    not cte.members @&gt; ARRAY[p.id1]
                    and cte.members @&gt; ARRAY[p.id2]
                )
        )
select  id
,       min(v) as min_id
from    cte
cross join lateral
        unnest(cte.members) v
group by
        id
order by
        id
;


Example at SQL Fiddle.  Hopefully someone else can contribute a simpler, more elegant, or better performing solution!