We call a graph G an IceCream of size K if G has exactly K+3…
We call a graph G an IceCream of size K if G has exactly K+3 vertices, K of which form a clique, and the other three vertices together with exactly two vertices of the clique form a cycle. The picture shows an ice cream graph of size 4 and 5, respectively. Consider the IceCream problem: Input: a graph G=(V,E) and an integer K>3. Output: a subset of K+3 vertices such that the induced subgraph is an IceCream of size K, and reports NO if such subset does not exist. Show that the IceCream problem is NP-complete.