# [r-t] q-sets

Sun Sep 10 17:59:45 UTC 2006

```
Richard Smith said  on 10/09/2006 12:04:
>
>> For it to be possible to connect all the blocks with the minimum number
>> of q-sets (i.e. n for 2n+1 blocks), it is sufficient that the graph
>> formed by these q-sets is connected.
>
> I think we need to require that every pair of connected
> q-sets have precisely one vertex in common -- in principle
> it is possible to have two vertices in common, even with
> size 3 q-sets (think OMI and 3H in PB6).

But if the q-sets span the graph they can only have one vertex in common.

>
>> Clearly we can arbitrarily remove
>> one edge from each q-set and the graph will be still be connected. It
>> now has 2n edges, and so is a tree.
>
> But the reverse isn't obviously true -- given an arbitrary
> tree with 2n edges (e.g. a spanning tree of the graph), we
> cannot obviously add another n edges to form a connected
> graph of q-sets.
>
> So it's not obvious (to me) that this implies that an extent
> covered by 2n+1 iblocks an always be connected by n q-sets.

That's not what I am saying - unless the 2n edges consist of 2 edges
each from n q-sets.

As a counterexample, consider 5 blocks with q-sets joining

1,2,3
1,2,4
1,2,5

--
Regards
Philip