\( \def\<#1>{\left<#1\right>} \newcommand{\CC}{\mathbf{C}} \newcommand{\disjpairs}{\mathcal{D}} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

Simpler proof of Theorem 14.2

Peter Melnichenko, a student of Vladimir Podolskii, has found a much simpler argument.

The adversary starts with an empty graph on $n$ vertices and maintains the connected components of the current graph. Hence, at the beginning, there are $n$ connected components = single vertices. At each step, the adversary uses the following strategy:

Hence, the first answer is always "yes", and the asked edge $e$ is added. If the next asked edge is $e'$, then the answer is "no" if $e\cap e'\neq\emptyset$, and is "yes" otherwise, etc.

It is easy to see that we will end up with a connected graph and that we maintain the following property:

In particular, to make the graph connected we need to ask all edges.
Indeed, in order to merge two components into one component, the decision tree must query all edges between these two components, and only gets a "yes" answer after all but one of these edges were already asked. $\Box$

S. Jukna, January 2015