A photonic band gap is determined by its boundaries, which are frequently computed by the Rayleigh-Ritz method, with the plane wave or the finite element basis functions. This method produces a sequence of upper bounds. Since there are no error estimates available on these approximations, the extent of the band gap is not accurately determined, particularly as this method is also known to suffer from a poor rate of convergence for the cases of interest. We adopt the method of intermediate problems to develop a procedure to calculate the lower bounds to the photonic band gap edges. The lower and the upper bounds supplement each other to determine a band gap with arbitrary accuracy, which is essential for designing the photonic band gap material. Computation of the lower bounds requires only slightly more effort than the upper bounds to produce the approximations with comparable accuracy. An alternative method to determine upper bounds is also developed in the process.