Graph theoretical techniques are demonstrated to be of considerable use in the search for stable arrangements of water clusters. inspired by the so-called "ice rules" that govern which hydrogen-bond networks are physically possible in the condensed phase, we use graphical techniques to generate a multitude of local minima of neutral and protonated water clusters using oriented graph theory. Efficient techniques to precisely enumerate all possible hydrogen-bonding topologies are presented. Empirical rules regarding favorable water neighbor geometries are developed that indicate which of the multitude of hydrogen-bonding topologies available to large water clathrates (e.g., 30 026 for (H2O)(20)) are likely to be the most stable structures. The cubic (H2O)(8) and dodecahedral (H2O)(20) clusters and their protonated analogues are treated as examples. In these structures every molecule is hydrogen bonded to three others, which lends to hydrogen-bonding topology fixing the cluster geometry. Graphical techniques can also be applied to geometrically irregular structures as well. The enumerated oriented graphs are used to generate initial guesses for optimization using various potential models. The hydrogen-bonding topology was found to have a significant effect on cluster stability, even though the total number of hydrogen bonds is conserved. For neutral clusters, the relationship between oriented graphs and local minima of several potential models appears to be one-to-one. The stability of the different topologies is rationalized primarily in terms of the number of nearest neighbor pairs that both have a free OH bond. This lends to the identification of water dodecahedra of greatest stability.