Every connected graph is a query graph
Peter M. Winkler · Journal of Graph Theory · 1987
Abstract Let V be a set of bit strings of length k, i.e., V ⊂ {0, 1}k. The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V, and {ū, v̄} is an edge of Q(V) if and only if no other w̄ ϵ V agrees with ū in all the positions in which v̄ does. If V represents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V). Ernst Leiss showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.