A note on the size of query trees

Abstract

We consider query trees of graphs with degree bounded by a constant, $d$. We give simple proofs that the size of a query tree is constant in expectation and $2^{O(d)}\log n$ w.h.p.