# Drawing graph decomposition as a tree

Let's say I have a triangle like this which is easily generated by pgf. \documentclass{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[
vertex/.style={circle, draw=blue!60, fill=blue!40, minimum size=2mm},
line/.style = {draw, thick}
]
\newcommand\mylength{30mm}
\coordinate (A) at ( 90: \mylength);
\coordinate (B) at (210: \mylength);
\coordinate (C) at (-30: \mylength);

\path [line] (A) -- (B);
\path [line] (B) -- (C);
\path [line] (C) -- (A);

\node [vertex] at (A) {1};
\node [vertex] at (B) {2};
\node [vertex] at (C) {3};

\end{tikzpicture}
\end{document}


And this is the diagram I want to draw:

          1
/ \
/   \
2-----3

/       \
/         \

1             1
\             \
\             \
2-----3             3


As some of you may notice it, the drawing is about a deletion-contraction recurrence. A triangle at the top node is decomposed into two subgraphs:

• The left child is obtained by deleting an edge 1-2
• The right child is obtained by contracting an edge 1-2 such that this edge shrinks to a single point by merging two endpoints 1 and 2 into a 'new 1' node, followed by deleting multiple edges.

I want to keep this process going until the tree reaches into much smaller graphs, so the final output will be much bigger. Even for the small tree of depth 1, I don't know what's the best way to draw such a tree. Any hints or suggestions?

Added: I used a triangle in this example because it's the simplest drawing that can be used as an example. The graph of interest can be any arbitrary graph and what I prefer is to wrap each graph in some kind of 'node' or 'box' and then connect each container node are connected as a node in a tree. What's the best way to do this?

Sorry for any confusion.

• If you know how to formulate a recursive algorithm, then this may be a related question. – user10274 May 18 '15 at 8:36
• I might know how to do it, but the thing is you need to establish rules for how to create nodes, where to put them and which ones should be connected. If you don't have rules or the rules are too ambiguous, then the only solution is to do each one manually. – Alenanno May 18 '15 at 10:01

## 2 Answers

May be you can define each graph as a TikZ pic. Each pic can be anything you want. If you use nodes inside them, as pic's name space is independent for each pic and all names are remembered, it's easy to join them.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,shapes,positioning,trees}

\tikzset{
vertex/.style  = {circle, draw=blue!60, fill=blue!40, minimum size=2mm},
all/.pic={
\node[vertex] (-1) {1};
\node[vertex, below left=1cm and 5mm of -1] (-2) {2};
\node[vertex, below right=1cm and 5mm of -1] (-3) {3};
\draw(-1)--(-2)--(-3)--cycle;
},
left/.pic={
\node[vertex] (-1) {1};
\node[vertex, below left=1cm and 5mm of -1] (-2) {2};
\node[vertex, below right=1cm and 5mm of -1] (-3) {3};
\draw(-1)--(-3)--(-2);
},
right/.pic={
\node[vertex] (-1) {1};
\node[vertex, below right=1cm and 5mm of -1] (-3) {3};
\draw(-1)--(-3);
},
}

\begin{document}
\begin{tikzpicture}

\pic (A) at (0,0) {all};
\pic (B) at (-2,-3) {left};
\pic (C) at (2,-3) {right};

\draw (A-2)--(B-1);
\draw (A-3)--(C-1);
\end{tikzpicture}
\end{document} A solution with Tikz.

## Output ## Code

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,shapes,positioning,trees}

\tikzset{
vertex/.style  = {circle, draw=blue!60, fill=blue!40, minimum size=2mm}
}

\begin{document}
\begin{tikzpicture}[%
no edge from this parent/.style={
edge from parent/.style={draw=none}},
level 1/.style={sibling distance=2cm},
level 2/.style={sibling distance=2cm},
level distance=2cm]

\node[vertex] (n1) {1}
child {node[vertex] (n2) {2}
child{node[vertex] (n4) {1}
child[no edge from this parent]{node[vertex] (n5) {2}}
child{node[vertex] (n6) {3}}
}
child[no edge from this parent]{node {}}
}
child {node[vertex] (n3) {3}
child[no edge from this parent]{node {}}
child{node[vertex] {1}
child[no edge from this parent]{node {}}
child{node[vertex] (n9) {3}}
}
};
\draw (n2) -- (n3);
\draw (n5) -- (n6);
\end{tikzpicture}
\end{document}

• Thank you for your quick response. It may be my fault not clarifying what I meant, but the graph of interest is not necessarily a triangle. It may be pentagram, rectangle, or any arbitrary graph. I just want to connect arbitrary graphs by edges to show them as part of a tree. – user19906 May 18 '15 at 9:28
• @user19906 Mh, well, then you need to express the rules to build such a graph in your question. Like: (1) is the nodes number what decides the position? (2) what numbers are connected by edges? Things like that. – Alenanno May 18 '15 at 9:32
• @user19906 Or would you like to repeat the above graph (being the same)? – Alenanno May 18 '15 at 9:35