A review and evaluation of graph theory approaches for their applicability to reliability analysis of water distribution networks is made. The procedures are examined in both a general sense and with respect to the networks previously reported in the literature. State enumeration, filtering, and heuristic procedures are considered. Most of the procedures were found to have computational requirements that make them inappropriate for use in water distribution analysis. A general procedure of assessing how far a particular network deviates from its maximum reliability for a given expenditure is suggested. A distinction between undirected and directed graphs is made in terms of techniques that can exploit either situation and in how portions of water distribution networks can be approximated by either case. Network transformation and inversion are also considered as a means of defining reliability and finding networks with maximum reliability. Recommendations are made as to how to combine various parts of the networks into sections, which can then be analysed by using procedures that best exploit the common features of the network in each section.