Message Boards Message Boards

Generate all subgraphs of a undirected graph?


Given an undirected graph G, is it possible to generate a list of all subgraphs of G which have a fixed number of edges with Mathematica?

POSTED BY: James Smith
7 months ago

Is having a fixed number of edges the only criterion, or do you also need them to be connected graphs?

If you only want the subgraphs with a given number of edges, regardless of whether they are connected, you can use Subsets

g = RandomGraph[{8, 12}];

edgelists = Subsets[EdgeList[g],{5}];

subgraphs = Subgraph[g, #] & /@ edgelists;

(* 792 *)
POSTED BY: Jason Biggs
7 months ago

Group Abstract Group Abstract