Electron phase space holes are analyzed in terms of solitary-wave solutions to the nonlinear Vlasov-Poisson equations in a collisionless plasma. Width-amplitude relations for one-dimensional and three-dimensional electron holes are derived to be inequalities that allow existence of the holes in regions to one side of a bound. The theoretical origin of the width-amplitude inequality is elucidated to show that the inequality nature is independent of specific functional forms of the solitary potential and ambient plasma distribution functions. Ion dynamics and effects of finite hole velocity and finite perpendicular size are subsequently included. Finally, we show that the electron holes reported by Franz et al. (2005) populate an allowed region in the solution space that is significantly away from the bounding curve. These electron holes evidence the accessibility of electron holes whose widths and amplitudes are only loosely constrained and open up the possibility of spontaneous generation of phase-space holes in turbulent fluctuations.