This work studies connectivity maintenance of mobile networks. A mobile network of interest consists of two types of nodes, pre-deployed (client) and intermediate nodes. Upon initial deployment of client nodes in a field, multiple stationary intermediate nodes are placed strategically to establish robust network connectivity. We study scenarios in which an initially connected network consisting of pre-deployed and intermediate nodes is exposed to mobility of the former. Two types of node mobility scenarios are investigated. The first scenario analyzes the bounds of mobility when pre-deployed nodes move at small scales. The bounds of node mobility preserving connectivity are derived through analysis and verified by simulations. The second scenario considers the movement of pre-deployed nodes beyond the bounds of the first scenario thereby breaking connected links and partitioning the connected network. This scenario then considers relocating the existing intermediate nodes in order to reestablish connectivity. A general formulation is proposed in the form of an optimization problem. We prove that the general formulation of the problem is NP-hard. Next, we turn our attention to a practical scenario in which the location of nodes is made available using GPS signals. We solve the problem of practical scenario in polynomial time and analyze the complexity of our solution. We also present comprehensive performance evaluation results of our proposed algorithm.