Graph Union

In dealing with graphs we often find it useful to consider the union of two graphs. Mathematically the transform is simple, but the concept is even more intuitive when viewing the adjacency matrix.

$$\left[ \begin{array}{ccc} 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 0 & ... ...0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]$$

Note that we specifically called this Graph Union and not Tree Union. Neither of the input graphs are required to be trees, and because no vertices in two distinct input graphs become adjacent, the resulting graph is disjoint and, thus, not a tree. We will consider $\mathit{Union}$ as being arbitrary arity, by defining $\mathit{Union}(G_1, G_2, \ldots, G_{n-1}, G_n) = \mathit{Union}(G_1, \mathit{Union}(G_2, \mathit{Union}(\ldots \mathit{Union}(G_{n-1}, G_n))))$. We will denote the union of two graphs $G_1$, $G_2$ as either $G_1 \cup G_2$ or $\mathit{Union}(G_1, G_2)$.