Question
Some of your friends work on wireless networks and they're at present studying the properties of a network of n mobile devices. As devices move around (actually as their human owners move around), they describe a graph at any point in time as follows: there is a node representing each of n devices, and there is an edge between device i and device j is the physical locations of i and j are more than 500 meters apart. (If so, we say that i and j are "in range" of each other.)
They'd like it to be case that the network of devices associated at all times, and so they've constrained motion of the devices to satisfy the following property: each device i is within 500 meters of at least n/2 of other devices. (We'll assume n is an even number.) What they'd like to know is: Does this property by itself assurance that the network will remain connected?