Understanding the "gap theorem" in geometric spanners I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:


  Intuitively: A set of directed edges satisfies the gap property, if the sources of any two distinct edges are "far" apart (relative to the shorter of the two edges)
  The gap property: Let $w \geq 0$ be a real number, and let $E$ be a set of directed edges in $\mathbb{R}^{d}$.
  We way that $E$ satisfies the $w-gap\ property$ if for any two distinct edges $(p,q)$ and $(r, s)$ in $E$, we have : $|pr| &gt; w \cdot min(|pq|, |rs|)$


Then (at the same page) comes the following Theorem:


  Let $S$ be a set of $n$ points in $\mathbb{R}^{d}$, and let $E \in S \times S$ be a set of directed edges that satisfies the $w-gap\ property$.
  1. If $w \geq 0$, then each points of $S$ is the source of at most one edge if $E$.
  2. if $w&gt;0$, then $wt(E)&lt;(1+2/w) \cdot wt(MST(S))\log n$ (where $MST(S)$ denotes a minimum spanning tree of $S$.
  3. [not relevant for the question]




Background and context

In the proof of the second claim, there is inner claim that there exists a set $E' \subseteq E$ that is of size $m/2$ such that $wt(E')&lt;(1+2/w) \cdot wt(MST(S))$.
Then comes an induction on $m$ in which the claim  $wt(E)&lt;(1+2/w) \cdot wt(MST(S))\log m$ for any set $E$ that has less that $m$ edges. (Note: $n$ can be replaced by $m$ because $m \leq n$ in every graph that satisfies the $w-gap\ property$). The main point of the induction is relaying on the existence of an subset $E'$ of $E$ which has at least $m/2$ edges, and weight $(1+2/w) \cdot wt(MST(S))$. Then any set $E$ can be partitioned into 2 sets  


$E'$ of weight $&lt;(1+2/w) \cdot wt(MST(S))$. (whose existence was proofed before)
$E \setminus E'$ of weight $&lt;(1+2/w) \cdot wt(MST(S)) \cdot \log m$. (according to the induction claim)


My question

Why is there the $\log m$? It seems to me that if the induction claim was "For every $E$ with less that $m$ edges $wt(E)&lt;(1+2/w) \cdot wt(MST(S))$". The same proof would get a better bound (without the $\log m$)
Let's write $C = (1+2/w) wt(MST(S))$. The set $E$ satisfies the $w$-gap property and has $m$ edges. It can be partitioned into 2 sets: 

One set is $E'$, which is a special subset of $E$. It is chosen such that we can easily prove that its weight is at most $C$. 

The other set $E''$ (which is $E \setminus E'$) has $m/2$ edges; we only know that it satisfies the $w$-gap property. By the induction hypothesis, the weight of $E''$ is at most $C \log(m/2)$. 

From this, it follows that the set $E$ has weight at most $C + C \log(m/2) = C \log m$.