Summary: A number of algorithms based on quasi-random graphs for generating perfect hash functions have been published. These include Sager’s mincycle algorithm, a modification by Fox et al. of it and finally probabilistic methods due to Z. J. Czech and the authors [Inf. Process. Lett. 43, No. 5, 257-264 (1992; Zbl 0772.68051)]. Each of these algorithms exploits different properties of graphs, such as being bipartite or being acyclic. In this paper, we formally justify the significance of these properties. Also we indicate causes of failure for some methods. In particular, we show that acyclicity of a graph plays a crucial role in finding order preserving perfect hash functions. It is a sufficient, but not necessary, condition for algorithms to actually find a perfect hash function. We provide some examples for which various published methods fail, taking exponential time to do so. Finally, based on our considerations of graph properties, we propose yet another method for generating perfect hash functions.