Message Boards Message Boards

Generate all subgraphs of a undirected graph?

GROUPS:

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
Answer
14 days 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

SeedRandom[42];
g = RandomGraph[{8, 12}];

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

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

Length@edgelists
(* 792 *)
POSTED BY: Jason Biggs
Answer
13 days ago

Group Abstract Group Abstract