Join of graphs

PDF p. 1: Section 2, first paragraph; PDF p. 2: Lemma 2.1, disconnected case

Let $t\ge 1$ be an integer and let $H_1,\dots ,H_t$ be finite simple graphs. Form their tagged disjoint graph family $D$, whose part for $i$ is $\{i\}\times V(H_i)$ and whose edges within that part are exactly $\{(i,u),(i,v)\}$ for $\{u,v\}\in E(H_i)$. The join $H_1\vee \cdots \vee H_t$ is the graph on $V(D)$ whose edges are the edges of $D$ together with every pair of vertices from distinct tagged parts. Thus each part induces a copy of its graph, and every vertex in one part is adjacent to every vertex in another part.

In particular, $G\vee H$ is obtained from vertex-disjoint copies of $G$ and $H$ by adding all edges between the copies. The construction also permits empty vertex sets, although the article's graph convention requires its graphs to be nonempty.

Graph and colouring conventions

Tagged graph families with anticomplete parts

The complete connection of two disjoint graphs

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Subgraphs, induced subgraphs and spanning subgraphs

Graph isomorphisms, automorphisms and graph complements

The tagged-family construction gives a finite vertex set, pairwise disjoint parts, and exactly the stated edges within each part. Adding the specified pairs from distinct parts gives a uniquely determined set of two-element subsets of that finite vertex set, hence a finite simple graph. The map $v\mapsto (i,v)$ is an isomorphism from $H_i$ to the subgraph induced by its tagged part. Any other choice of pairwise disjoint isomorphic copies gives an isomorphic join by applying the chosen isomorphisms part by part; within-part adjacency and all cross-part adjacency are preserved and reflected. For $t=2$, the construction is the complete connection of the two tagged copies. For $t=1$, it is a tagged copy of $H_1$.