Thread: Minimal embeddable Graph

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

If G isn't complete, then minimal graph that is not embeddable into G exist and have at least vertices. Now you have to add some edges (with new vertices) to the maximum clique (of course you can also remove some edges from that).