Some friends of yours work on wireless networks, andthey’re currently studying t

Question

Some friends of yours work on wireless networks, andthey’re currently studying the properties of a network ofn mobile devices. As the devices move around (actually, astheir human owners move around), they define a graph at any pointin time as follows: there is a node representing of the ndevices, and there is an edge between device i and devicej if the physical locations of i and jare no more than 500 meters apart. (If so, we say that iand j are “in range” of each other).

               They’d like it to be the case that the network of devices isconnected at all times, and so they’ve constrained the motionof devices to satisfy the following property: at all times, eachdevice i is within 500 meters of at least n/2 ofthe other devices (We’ll assume n is an evennumber). What they’d like to know is: Does this property byitself guarantee that the network will remain connected?

               Here’s a concrete way to formulate the question as a claimabout graphs.

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

               Decide whether you think the claim is true or false and give arpoff of either the claim or its negation. Hint: It might be easyto prove by contradiction.

Explanation / Answer

Claim: Let G be a graph on n nodes, where n is an evernumber. If every node of G has degree at least n/2 , then G isconnected. The given claim is True: We can prove this by contradiction. Proof: Let us assume that the graph G is not connected. For the graph G to be not connected, there must exist at least onenode which is isolated from the remaining graph [i.e. no edges tothe other part of the graph] But from the statement every node has to have edges to at least n/2other nodes.... Therefore these (n/2 + 1) form one component (say A) which isdisconnected from the other components. if (n/2 +1) nodes form a component , the number of nodesremaining to form the other component is n -(n/2 + 1) = n/2 -1 These n/2 -1 nodes cannot form a component B among themselves asevery node in G should have edges to n/2 other nodes. because there are only n/2 -1 nodes in B....every node in B shouldhave atleast one edge to component A. Therefore every node in B is connected to at least one node inA. Therefore A and B are connected which contradicts ourassumption. Therefore our assumption that G is disconnected is wrong whichproves that if G follows the given conditions, G must beconnected.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.