# How to calculate and display possible graphs from 3 directed branches?

I have 3 directed branches and I want to create all possible graphs that can be created from these branches with the condition that each branch is used once.

Q1: How can I do create and graph them? Here are some example graphs: Q2: Same as Q1 but now add one more condition that the branch a and branch b are connected as in the image below. • What exactly is a branch here, and how is it implemented? Jun 20 at 22:05
• @thorimur it's something like this Graph[{1 \[DirectedEdge] 2, 2 \[DirectedEdge] 3, 3 \[DirectedEdge] 1}] Jun 20 at 22:10
• hmm ok, so are you asking for all possible graphs with 3 directed edges? if so do you have any constraint on the number of vertices? also are the edges and vertices labeled? Jun 20 at 22:10
• @thorimur yes, all possible graphs with 3 directed edges. I don't have any constraint in the number of vertices but from 3 branches there is a maximum of 6 vertices. I labeled edges to make it clear that they're different. I think you could also label the vertices if an edge. Jun 20 at 22:15
• @thorimur for example 1 and 2 are two vertices of a then the edge a is always from 1 to 2. I edited and added some examples. Jun 20 at 22:40

edges = {"A" -> "B", "C" -> "D", "E" -> "F"};

styledlabelededges = MapThread[Labeled[Style[#, #2], #3] &,
{edges,
{Red, Green, Blue},
Style[#, 16, Background -> White] & /@ {"a", "b", "c"}}];

g0 = Graph[styledlabelededges,
ImageSize -> 400,
VertexLabelStyle -> Medium,
VertexLabels -> "Name",
GraphLayout -> "CircularEmbedding"] ClearAll[vContract]
vContract[g_] := Graph @@
({EdgeList[g], Options[g]} /. #[] -> #[] /. #[] -> #) &

vreplacements = {{"B", "E"}, {"B", "F"}, {"B", "C"}, {"A", "D"}};

Grid[Partition[vContract[g0] /@ vreplacements, 2], Dividers -> All] • When B, E are contracted, the branch a could be disconnected as in your plot but it can also connect to any other node. How can I do that? How can I plot all cases also when 3 branches are connected? I think you mean to apply contract in series? Jun 20 at 23:34
• @anhnha, corrected the labels and styles.
– kglr
Jun 20 at 23:45
• your image shows the contracted nodes with two letters like {B, E} but it doesn't appear when I run it. Jun 20 at 23:53
• @anhnha, please try the current version.
– kglr
Jun 20 at 23:57
• nice, the code is complex but I'll try to reprocedure it. Jun 21 at 0:02

The following is a brute force solution, but it is easy to understand:

This is the starting graph:

g0 = Graph[{"a" -> "b", "c" -> "d", "e" -> "f"}];


You want to contract vertices in all possible ways. For simplicity, we will use IGVertexContract from IGraph/M, as it can handle multiple contractions simultaneously.

Needs["IGraphM"]


Contracting the two endpoints of an existing edge (such as a -> b) is not allowed:

vertices = VertexList[g0]

disallowed = Partition[vertices, 2]
(* {{"a", "b"}, {"c", "d"}, {"e", "f"}} *)


These are the allowed contractions:

possibleContractions = Complement[Subsets[vertices, {2}], disallowed]
(* {{"a", "c"}, {"a", "d"}, {"a", "e"}, {"a", "f"}, {"b", "c"},
{"b", "d"}, {"b", "e"}, {"b", "f"}, {"c", "e"}, {"c", "f"},
{"d", "e"}, {"d", "f"}} *)


We can get all combinations with Subsets[possibleContractions]. However, given a vertex, we may only contract it with one other vertex, not multiple one. Thus, we need a helper function to detect multiple contractions:

disjointQ[list_] := Length[Union @@ list] == Length[Join @@ list]


These are the allowed contractions: Select[Subsets[possibleContractions], disjointQ].

IGVertexContract[g0, #, GraphStyle -> "VintageDiagram"] & /@
Select[Subsets[possibleContractions], disjointQ]
`

Here's a screenshot of the first few results: Note that graphs with reciprocal edges are also generated. You did not make it clear if you need them. If not, just filter them out.