Dwarf planets and giant planets' moons may record the original composition of the solar or planetary nebula. Previous models assumed essentially Earth-like silicate-metal cores surrounded by ice. Inner density models of the rocky cores of differentiated Ganymede and Titan, the largest icy moons in the solar system indicate the presence of a low-density component in addition to silicates and metal sulfide. Carbonaceous matter akin to coal formed from abundant organic matter in the outer solar system is a likely low-density component. We tested this hypothesis and found that rocky core densities in dwarf planets and icy moons are consistent with a mixture of chondritic silicate-sulfide rocks and a rock-free precursor composed of ices and carbonaceous matter in near-solar proportions. Thermal models taking into account the presence of carbonaceous matter are performed to evaluate its effects on the present-day structure of icy moons and dwarf planets.