We propose a new lower bound on the number of frequencies required to meet the frequency demands in a cellular network. It extends Gamst's (1986) work by devising a procedure of frequency insertion, which makes the best of unexploited frequency spaces between the assigned frequencies. Our lower bound is claimed to have much wider and easier real-world applicability due to its relaxed prerequisite condition. Furthermore, it is shown via an illustrative example to be much tighter than its previous counterpart.