How can one ensure this property of this decision tree?

Question

I am reading Evasiveness of Graph Properties and Topological Fixed-Point Theorems.

First the author defines: $G(V_0)$ to be the set of all graphs with the vertices described in $V_0$. He then defines a graph property to be a graph property to be some function:

$$h : G( V_0) \to \{1, 0 \}$$

Where (I believe) $h(X) = 0$ means a graph $X$ doesn't have the property and $h(X) = 1$ means $X$ does have the property.

He then states that a monotone property is one that if $G'$ is a subgraph of $G$ then $h(G') \leq h(G)$.

Now the simplex induced by $h$, (denoted $\Delta_h$) is the set of all edge subsets such that $h(X) = 0$. (page 16).

Now we wish to determine if a graph has a property $h$ and we may ask an oracle whether or not there exists an edge between two vertices of our choice, this gives us a decision tree. At the end we output $1$ or $0$ if the property is satisfied or not.

The following theorem is proposed on page 19 (with a proof that follows):

Let $V_0$ be a finite set. Let $$h : G(V_0) \to \{0, 1\}$$ be a monotone increasing function. If $\Delta_h$ is non-empty, it is collapsable.

Evasive means we need to check every edge before we can come to a conclusion, hence if every edge needs to be checked there must exist a decision tree where the depth is $ \leq (|V_0||V_0 - 1|)/2$.

The proof then goes on to state that yet another tree $T'$ can be constructed that satisfies:

1. The paths in $T'$ do not have repeated edges. (Ok, I guess we just don't repeat edges while questioning)
2. Every path has exactly length $(|V_0||V_0-1|)/2 - 1$

I don't understand number 2. How can we guarantee this?

Answer 1

To modify the tree $T$ to have the second property, repeat the following step:

1. If there is some "Y" leaf at height less than $\frac{n(n-1)}{2}-1$, replace it by an $\{i,j\}$ node (where $\{i,j\}$ is an edge we haven't looked at yet), and label both of its children "Y".
2. If there is some "N" leaf at height less than $\frac{n(n-1)}{2}-1$, replace it by an $\{i,j\}$ node (where $\{i,j\}$ is an edge we haven't looked at yet), and label both of its children "N".

This step doesn't change the output of the decision process: instead of giving an answer of "X", we look at $\{i,j\}$ and say "X" whether or not the edge is present. But it replaces a leaf at height $k$ with two leaves at height $k+1$, so repeating the step will eventually put all leaves at height $\frac{n(n-1)}{2}-1$.

To put it another way: if we get enough information to decide $h$ from looking at fewer than $\frac{n(n-1)}{2}-1$ edges, we just look at some more edges that we haven't looked at, ignore the information we get from them, and make the decision we were going to make anyway.