We perform a detailed theoretical study of the edge fracture instability, which commonly destabilizes the fluid-air interface during strong shear flows of entangled polymeric fluids, leading to unreliable rheological measurements. By means of direct nonlinear simulations, we map out phase diagrams showing the degree of edge fracture in the plane of the surface tension of the fluid-air interface and the imposed shear rate, within the Giesekus and Johnson-Segalman models, for different values of the nonlinear constitutive parameters that determine the dependencies on the shear rate of the shear and normal stresses. The threshold for the onset of edge fracture is shown to be relatively robust against variations in the wetting angle where the fluid-air interface meets the hard walls of the flow cell, whereas the nonlinear dynamics depend strongly on the wetting angle. We perform a linear stability calculation to derive an exact analytical expression for the onset of edge fracture, expressed in terms of the shear-rate derivative of the second normal stress difference, the shear-rate derivative of the shear stress (sometimes called the tangent viscosity), the jump in the shear stress across the interface between the fluid and the outside air, the surface tension of that interface, and the rheometer gap size. (The shear stress to which we refer is sigma(xy) with (x) over cap being the flow direction and (y) over cap being the flow-gradient direction. The interface normal is in the vorticity direction (z) over cap.) Full agreement between our analytical calculation and nonlinear simulations is demonstrated. We also elucidate in detail the mechanism of edge fracture and finally suggest a new way in which it might be mitigated in experimental practice. We also suggest that, by containing the second normal stress difference, our criterion for the onset of edge fracture may be used as a means to determine that quantity experimentally. Some of the results in this paper were first announced in an earlier letter [E. J. Hemingway, H. Kusumaatmaja, and S. M. Fielding, Phys. Rev. Lett. 119, 028006 (2017)]. The present paper provides additional simulation results, calculational details of the linear stability analysis, and more detailed discussion of the significance and limitations of our findings. (C) 2019 The Society of Rheology.