High-dynamic-range surface photometry in a companion paper makes possible accurate measurement of the stellar light deficits L(def) and mass deficits M(def) associated with the cores of elliptical galaxies. We show that L(def) correlates with velocity dispersions sigma of the host galaxy bulge averaged outside the central region that may be affected by a supermassive black hole (BH). We confirm that L(def) correlates with BH mass M(center dot). Also, the fractional light deficit L(def)/L() correlates with M(center dot)/M(), the ratio of BH mass to the galaxy stellar mass. All three correlations have scatter similar to or smaller than the scatter in the well-known correlation between M(center dot) and sigma. The new correlations are remarkable in view of the dichotomy between ellipticals with cores and those with central extra light. Core light deficit correlates closely with M(center dot) and sigma, but extra light does not. This supports the suggestion that extra light Es are made in wet mergers with starbursts whereas core Es are made in dry mergers. After dry mergers, cores are believed to be scoured by BH binaries that fling stars away as their orbits decay or by BHs that sink back to the center after recoiling from anisotropic gravitational radiation emitted when they merge. Direct evidence for these mechanisms has been elusive. We interpret the new correlations as the "smoking gun" that connects cores with BHs. Together, the M(center dot) - sigma and M(center dot) - L(def) correlations give us two independent ways to estimate BH masses in core Es.