---
title: "Unions and Products of Graphs"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/union-product.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/union-product.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Standard Constructions for Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/operation.md"}
next: {"title": "Converting between Graphs and Digraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/conversion-graph-digraph.md"}
intrinsics:
  - {"name": "Union", "signature": "Union(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "Union", "signature": "Union(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "join", "signature": "G join H: GrphDir, GrphDir -> GrphDir"}
  - {"name": "join", "signature": "G join H: GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "EdgeUnion", "signature": "EdgeUnion(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "EdgeUnion", "signature": "EdgeUnion(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "CompleteUnion", "signature": "CompleteUnion(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "CompleteUnion", "signature": "CompleteUnion(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "CartesianProduct", "signature": "CartesianProduct(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "CartesianProduct", "signature": "CartesianProduct(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "LexProduct", "signature": "LexProduct(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "LexProduct", "signature": "LexProduct(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "TensorProduct", "signature": "TensorProduct(G, H): GrphDir, GrphDir -> GrphDir"}
  - {"name": "TensorProduct", "signature": "TensorProduct(G, H): GrphUnd, GrphUnd -> GrphUnd"}
  - {"name": "^", "signature": "G ^ n: GrphUnd, RngIntElt -> GrphUnd"}
---

<a id="union-product"></a>
<a id="graph-sec-union"></a>
# Unions and Products of Graphs

The support and vertex/edge decorations of the original graphs are *not* retained in the graph resulting from applying any of the union functions below.

<a id="function-union-grphund-grphund"></a>
## `Union(G, H): GrphUnd, GrphUnd -> GrphUnd`

<a id="function-union-grphdir-grphdir"></a>
## `Union(G, H): GrphDir, GrphDir -> GrphDir`

<a id="operation-op-join-grphdir-grphdir"></a>
## `G join H: GrphDir, GrphDir -> GrphDir`

<a id="operation-op-join-grphund-grphund"></a>
## `G join H: GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex sets $V(G)$ and $V(H)$, respectively, construct their union, i.e. the graph with vertex-set $V(G) \cup V(H)$, and edge-set $E(G) \cup E(H)$.

<a id="function-edgeunion-grphdir-grphdir"></a>
## `EdgeUnion(G, H): GrphDir, GrphDir -> GrphDir`

<a id="function-edgeunion-grphund-grphund"></a>
## `EdgeUnion(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ having the same number of vertices, construct their edge union $K$. This construction identifies the $i$-th vertex of $G$ with the $i$-th vertex of $H$ for all $i$. The edge union has the same vertex-set as $G$ (and hence as $H$) and vertices $u$ and $v$ of $K$ are adjacent if and only if either $u$ and $v$ are adjacent in $G$ or $u$ and $v$ are adjacent in $H$.

<a id="function-completeunion-grphdir-grphdir"></a>
## `CompleteUnion(G, H): GrphDir, GrphDir -> GrphDir`

<a id="function-completeunion-grphund-grphund"></a>
## `CompleteUnion(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, construct the complete union of $G$ and $H$. This graph consists of the union of $G$ and $H$ (`Union(G, H)`), together with edges $uv$, for all $u$ in $V(G)$ and all $v$ in $V(H)$.

<a id="function-cartesianproduct-grphdir-grphdir"></a>
## `CartesianProduct(G, H): GrphDir, GrphDir -> GrphDir`

<a id="function-cartesianproduct-grphund-grphund"></a>
## `CartesianProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the product $K = G\times H$ of $G$ and $H$. The product has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when either

**(a)**
$u_1 = v_1$ and $u_2\ {\operatorname{adj}}v_2$, or

**(b)**
$u_2 = v_2$ and $u_1\ {\operatorname{adj}}v_1$.

<a id="function-lexproduct-grphdir-grphdir"></a>
## `LexProduct(G, H): GrphDir, GrphDir -> GrphDir`

<a id="function-lexproduct-grphund-grphund"></a>
## `LexProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the lexicographic product $K$ of $G$ and $H$. The lexicographic product has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when either

**(a)**
$u_1\ {\operatorname{adj}}v_1$, or

**(b)**
$u_1 = v_1$ and $u_2\ {\operatorname{adj}}v_2$.

<a id="function-tensorproduct-grphdir-grphdir"></a>
## `TensorProduct(G, H): GrphDir, GrphDir -> GrphDir`

<a id="function-tensorproduct-grphund-grphund"></a>
## `TensorProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the tensor product $K$ of $G$ and $H$. This graph has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when $u_1\ {\operatorname{adj}}v_1$ and $u_2\ {\operatorname{adj}}v_2$.

<a id="operation-op-pow-grphund-rngintelt"></a>
## `G ^ n: GrphUnd, RngIntElt -> GrphUnd`

Given a graph $G$ and a positive integer $n$, construct the $n$-th power $K$ of $G$. This graph has the same vertex-set as $G$, and vertices $u$ and $v$ of $K$ are adjacent if and only if the distance between $u$ and $v$ in $G$ is less than or equal to $n$.
