Given a graph G. A graph H is called embeddable into G if a subset of G is equal to H.

For a given graph G we want to find the minimal (least number of edges (but of course at most as many vertices as G)) graph that is not embeddable.

Can someone tell me what the general approach to those probelms is (if there is)?

In the specific case G consists of c "core" vertices which form a complete subgraph and x outer vertices each connected exactly to all os the c core vertices.

I already figured out that this specific graph is complete up to the missing vertices between the x outer vertices. Therefore those must be targetes, eg with cycles or the like but I am not quite sure.

Thanks,

Trome