[r-t] q-sets

[Philip Saddleton]

Richard Smith said  on 10/09/2006 12:04:
> Philip Saddleton wrote:
> 
>> 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
http://www.saddleton.freeuk.com/