# Finding induced subgraphs that are also trees

Given a graph $$G$$ with $$n$$ vertices, I need to find a subgraph consisting of $$m$$ vertices $$\{v_1,\ldots,v_m\}$$, and the induced subgraph of this subgraph should also be a tree.

For example, suppose $$G$$ is a $$3\times3$$ grid graph, and the subgraph should include vertices $$\{6,8,1\}$$. Shown below is an example of a subgraph (edges in green) which includes these vertices.

However, its induced subgraph is

which is not a tree.

A solution for this specific example would be;

and its induced subgraph,

which is a tree.

• why is it that the subgraph formed by green edges in the second picture not a tree?
– kglr
Commented May 28, 2023 at 19:44
• the subgraph is a tree, however the induced subgraph, which includes all the edges between the vertices in the original graph, is not. Commented May 28, 2023 at 19:49
• According to the definition in the link, the only induced subgraph formed by vertices $\{6,8,1\}$ in your example is the graph with vertex list $\{6,8,1\}$ and no edges.
– kglr
Commented May 28, 2023 at 19:49
• Ah ok, i understand the confusion..i should've been more clear. The induced subgraph is formed from all the vertices in the subgraph, not just $\{6,8,1\}$. Commented May 28, 2023 at 19:56
• thank you Dotman.
– kglr
Commented May 28, 2023 at 19:59

Update:

A less-brute force modification:

ClearAll[findInducedSubtree]
findInducedSubtree[g_, vlst_] /; {} === FindCycle[Subgraph[g, vlst], ∞, 1] :=
Module[{k = 1, res = {}},
While[{} === (res = Flatten @
Map[If[TreeGraphQ @ #, #, {}] & @ Subgraph[g, Join[vlst, #]] &]@
Subsets[Complement[VertexList@g, vlst], {k++}])];
MinimalBy[VertexCount] @ res]


Examples:

vlst = {6, 8, 1};

gg = GridGraph[{3, 3},
PlotTheme -> "ThickEdge", VertexLabels -> Automatic,
VertexSize -> (Alternatives @@ vlst -> Medium)];

Row[HighlightGraph[gg, #, ImageSize -> 300] & /@
findInducedSubtree[gg, vlst]]


vls = {21, 2, 3, 7, 35, 11, 32, 26, 30, 16, 8, 25};

gg6 = GridGraph[{6, 6}, PlotTheme -> "ThickEdge",
VertexLabels -> Automatic,
VertexSize -> (Alternatives @@ vls -> Medium)];

HighlightGraph[gg6, Subgraph[gg6, vls], ImageSize -> 400]


pics = HighlightGraph[gg6, #, ImageSize -> 400] & /@
findInducedSubtree[gg6, vls];

Multicolumn[pics, 4]


SeedRandom[1];

rg = RandomGraph[{30, 50}, PlotTheme -> "ThickEdge",
VertexLabels -> Automatic, GraphHighlightStyle -> "Thick",
EdgeStyle -> AbsoluteThickness[5],
VertexSize -> (Alternatives @@ vls -> Large)];


A vertex list that does not induce a subgraph with cycles:

While[{} =!= FindCycle[
Subgraph[rg, vls = RandomSample[Range@30, 12]], ∞, 1]];
vls

{3, 10, 14, 27, 17, 28, 18, 8, 9, 23, 4, 20}

HighlightGraph[rg, Subgraph[rg, vls], ImageSize -> 500]


trees = findInducedSubtree[rg, vls];

Row[HighlightGraph[rg, #, ImageSize -> 600] & /@ trees]


A brute-force approach:

ClearAll[selectSubgraphs]

selectSubgraphs[g_, vlst_] := Select[TreeGraphQ] @
Map[Subgraph[g, #] &] @
Select[ContainsAll @ vlst] @
Subsets[VertexList @ g, {Length @ vlst, VertexCount @ g}]


Examples:

vlst = {6, 8, 1};

gg = GridGraph[{3, 3},
PlotTheme -> "ThickEdge", VertexLabels -> Automatic,
VertexSize -> (Alternatives @@ vlst -> Medium)];

Multicolumn[HighlightGraph[gg,  #] & /@ selectSubgraphs[gg, vlst], 4]


If desired, select the subgraphs with minimum number of vertices:

Row[HighlightGraph[gg, #, ImageSize -> 300] & /@
MinimalBy[VertexCount]@selectSubgraphs[gg, vlst]]


• This is nice, thank you. However its not really applicable in cases beyond $5\times5$. Im looking to analyse this problem upto $10\times10$ case. Hence I'm not marking this as the answer (yet). Commented May 29, 2023 at 12:31
• is your base graph always a grid graph ?
– kglr
Commented May 29, 2023 at 13:31
• Not necessarily…. However It would be nice to have a solution that at least works on grid graphs Commented May 29, 2023 at 14:15
• Dotman, please see the update.
– kglr
Commented May 29, 2023 at 14:59
• your second example is wrong. 6,16 and 17,27 are neighbours, hence the induced subgraph is not a tree Commented May 29, 2023 at 15:06