Show all subgraphs which don't contain a specific subgraph

Question

Is there a way to generate a list of all $m$ subgraphs $g_1,g_2,\dots,g_m$ of a graph $G$ which don't contain a specified graph isomorphic to the graph $H$?

For example, all subgraphs of the complete graph which don't contain a 3-path $\Pi_3$ (3 edges, 4 vertices, in a path).

I can see Subgraph[g,patt], which according to the documentation

gives the subgraph generated by the vertices and edges that match the pattern patt.

But what is the usage?

I can see IGraphM has IGSubisomorphicQ which can test for subgraph containment. So one would then simply need to list all subgraphs effectively. Is this done with the power set of the edges?

Answer 1

To generate all the subgraphs of the complete graph:

kgraph = CompleteGraph[4];
HighlightGraph[kgraph, #] & /@ (Graph[VertexList@#, #] & /@ 
   Subsets[EdgeList[kgraph]])

and so on.

Then, to test for the subgraph, having loaded IGraph, use

subgraph = PathGraph[{1, 2, 3, 4}];
graphs=Graph[VertexList@#, #] & /@ Subsets[EdgeList[kgraph]];
Transpose[{graphs, 
IGSubisomorphicQ[subgraph, #] & /@ graphs}]

part of the output of which is displayed here: