Welcome to Android Central! Which phone, and which gallery app? What you're describing sounds like a Picasa or Google Photos icon, which would imply the photos are saved in your Google Photos cloud. Oftentimes, cloud photos can't be deleted using the stock Gallery app -- you need to use the Google Photos app, or go to the Google Photos website.
Go to photos.google.com -- do you see the same photos there?