\(
\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:
- When asked about an edge $e$, he answers "yes", only if $e$ joins two components and is the last unasked edge between these components.
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:
- At each step, in each component all edges were already asked.
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$