Optimality proof

If INvalue = Min-Int((worst explored INvalue)/2), where MinInt(x) returns the least integer greater than x, then the INvalue is optimal.

Proof. In fact, if the IN value for node A is k, then every node belonging to the dense MANET is within k hops from node A (and there exists at least one node, let us say C, whose shortest path towards node A is k hops long). Let us ab absurdo suppose that the IN value for node B is j < k/2. Then, there would exist a path connecting nodes A and C passing through node B, and its length would be at most 2j (< k). This clashes with the given hypothesis.