# Counterexample or proof of 2-tuple set uniqueness

I am trying to find a proof or (more likely) counterexample of the following problem:

Given a list of same sized unique sets produce a list of 2-tuple counts contained within.
Using the 2-tuple counts it is possible to reproduce the original sets?

For example...

The following same sized unique sets:

{1, 2, 3, 6}
{1, 2, 4, 5}
{1, 3, 4, 6}
{2, 3, 5, 6}
{2, 4, 5, 6}
{3, 4, 5, 6}


Contains these 2-tuple counts:

(1, 2) = 2 (2 sets contains both 1 & 2)
(1, 3) = 2 (2 sets contains both 1 & 3)
(1, 4) = 2 (etc)
(1, 5) = 1
(1, 6) = 2
(2, 3) = 2
(2, 4) = 2
(2, 5) = 3
(2, 6) = 3
(3, 4) = 2
(3, 5) = 2
(3, 6) = 4
(4, 5) = 3
(4, 6) = 3
(5, 6) = 3


Using these 2-tuple counts, there is only one possible list of sets which could occur (the original list of sets - found by brute force).

I have no idea where to begin with a proof, and am just trying random combinations hoping to find a counterexample.

Any assistance would be greatly appreciated.

EDIT:

As Petar Ivanov has identified, I am only concerned with sets of a known size (the same as the original).

-

## migrated from stackoverflow.comNov 15 '11 at 13:33

This question came from our site for professional and enthusiast programmers.

Are you given the size of the first sets? – JohnPS Nov 15 '11 at 5:45
@JohnPS: Yes, size of the sets to reconstruct is known – threenplusone Nov 15 '11 at 5:51

Here is a counter example:

Family of sets 1:

{10, 1, 2}
{10, 3, 4}
{20, 1, 3}
{20, 2, 4}


Family of sets 2:

{10, 1, 3}
{10, 2, 4}
{20, 1, 2}
{20, 3, 4}


This example can easily be extended to arbitrary set sizes. E.g. for 4 just replace 10 with 10, 11 and 20 with 20, 21, etc.

-
+1: Just checked, and it works out. – bdares Nov 15 '11 at 6:12
Perfect, thank you. – threenplusone Nov 15 '11 at 6:13