Water distribution networks, like other engineering systems, are subjected to random.failures. The failures may occur in the elements of the network (mostly pipes) or in the nodes (pipe junctions and demand nodes). Since a breakdown in water supply is not acceptable for more than a few hours, the network should be invulnerable to some extent, that is, it must include several independent alternatives of water supply to every consumer. Adopting an invulnerability degree of two alternative supplies, a new methodology is presented for the least-cost design of water distribution networks. According to this methodology the design process is controlled by the designer via three distinct stages. In the first stage the alternative paths are allocated using graph theory algorithms. In the second stage the minimum hydraulic capacity (diameters) of each path is determined using a linear programming model, and in the third stage the solution is tested by a network solver for various demand patterns. An example for the first stage and its relevant graph theory algorithms are included.