Question

Assume we are working on wireless networks, and we are studying the properties of a network of n mobile devices. As the devices move around (actually, as their human owners move around), we define a graph at any point in time as follows: there is a node representing each of the n devices, and there is an edge between device i and device j if the physical locations of i and j are no more than 500 meters apart. (If so, we say the i and j are "in range" of each other.)

To ensure that the network of devices is connected at all times, we constrained the motion of the devices to satisfy the following property: at all times, each device i is within 500 meters of at least n/2 of the other devices, assuming n is even. What we would like to know is: Does this property by itself guarantee that the network will remain connected?

Here is a concrete way to formulate the question as a claim about graphs.

Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has degree at least n/2, then G is connected.

Decide whether the claim is true or false, and give a proof of either the claim or its negation.

Answer 1

This problem can be interpreted as the following graph theory problem:

If G is a graph with n vertices where n is an even number, and if every vertex has degree at least n/2, then G must be a connected graph.

We prove this claim by the method of contradiction.

Let us assume that G is not connected. Then G must have at least two components. We name these two components C1 and C2.
Let us consider a vertex in C1. Since the degree of this vertex is at least n/2, we must have at least n/2 vertices which are neighbors of this vertex, and all of these vertices must be in C1. So C1 should have at least (n/2)+1 vertices.
By the same logic C2 should also have (n/2)+1 vertices.
So, the total number of vertices is (n/2)+1+(n/2)+1=n+2.

But the graph was assumed to have n vertices. So this is a contradiction.

Hence the graph G must be connected.

So, the given network will always remain connected.