Join (graph theory)

In graph theory, the join operation is a graph operation that combines two graphs by connecting every vertex of one graph to every vertex of the other. The join of two graphs $G_{1}$ and $G_{2}$ is denoted $G_{1} + G_{2}$ , $G_{1} \lor G_{2}$ , or $G_{1} \nabla G_{2}$ .

Definition

Let $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ be two disjoint graphs. The join $G_{1} + G_{2}$ is a graph with:

Vertex set: $V (G_{1} + G_{2}) = V_{1} \cup V_{2}$
Edge set: $E (G_{1} + G_{2}) = E_{1} \cup E_{2} \cup {u v ∣ u \in V_{1}, v \in V_{2}}$

In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in $G_{1}$ to every vertex in $G_{2}$ .

Examples

Several well-known graph families can be constructed using the join operation.

Complete bipartite graph: $K_{m, n} = {\overline{K}}_{m} + {\overline{K}}_{n}$ (join of two independent sets).
Wheel graph: $W_{n} = C_{n} + K_{1}$ (join of a cycle graph and a single vertex).
Star graph: $S_{n + 1} = {\overline{K}}_{n} + K_{1}$ (join of a $n$ vertex empty graph and a single vertex).
Fan graph: $F_{m, n} = P_{n} + {\overline{K}}_{m}$ (join of a path graph with an empty graph).
Complete graph: $K_{n} = K_{m} + K_{n - m}$ (join of two complete graphs whose orders sum to $n$ ).
Cograph: Cographs are formed by repeated join and disjoint union operations starting from single vertices.
Windmill graph: $D_{n}^{(m)} = m K_{n - 1} + K_{1}$ (join of $m$ copies of the complete graph on $n - 1$ vertices with a single vertex).

Properties

Basic properties

The join operation is commutative for unlabeled graphs: $G_{1} + G_{2} ≅ G_{2} + G_{1}$ .

If $G_{1}$ has $p_{1}$ vertices and $q_{1}$ edges, and $G_{2}$ has $p_{2}$ vertices and $q_{2}$ edges, then $G_{1} + G_{2}$ has $p_{1} + p_{2}$ vertices and $q_{1} + q_{2} + p_{1} p_{2}$ edges. If $p_{1} > 0$ and $p_{2} > 0$ then $G_{1} + G_{2}$ is connected ( $K_{p_{1}, p_{2}}$ is a subgraph).

Chromatic number

The chromatic number of the join satisfies:

χ (G_{1} + G_{2}) = χ (G_{1}) + χ (G_{2})

.

This property holds because vertices from $G_{1}$ and $G_{2}$ must use different colors (as they are all adjacent to each other), and within each original graph, the minimum coloring is preserved. It was used in a 1974 construction by Thom Sulanke related to the Earth–Moon problem of coloring graphs of thickness two. Sulanke observed that the join $C_{5} + K_{6}$ is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.

$G_{1} + G_{2}$ is color critical if and only if $G_{1}$ and $G_{2}$ are both color critical.

References

1 2 3 Bollobás, Béla (1998). Modern Graph Theory. Graduate Texts in Mathematics. Springer. p. 7. ISBN 0-387-98491-7.
1 2 3 Beineke, Lowell; Wilson, Robin; Cameron, Peter. "Introduction". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Topics in Algebraic Graph Theory. Encyclopedia of Mathematics and Its Applications. Vol. 102. Cambridge University Press. p. 6. ISBN 0-521-80197-4.
1 2 3 Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. Elsevier. p. 58.
1 2 3 4 Weisstein, Eric W. "Graph Join". mathworld.wolfram.com. Retrieved 2025-10-30.
1 2 West, Douglas Brent (2001). Introduction to graph theory (2. ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0130144003.
↑ Gethner, Ellen (2018). "To the moon and beyond". In Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.). Graph theory—favorite conjectures and open problems. 2. Problem Books in Mathematics. Cham: Springer. pp. 115–133. ISBN 978-3-319-97684-6. MR 3930641.

External links

Weisstein, Eric W. "Graph Join". MathWorld.

[bollobas-1] 1 2 3 Bollobás, Béla (1998). Modern Graph Theory. Graduate Texts in Mathematics. Springer. p. 7. ISBN 0-387-98491-7.

[TAGT-2] 1 2 3 Beineke, Lowell; Wilson, Robin; Cameron, Peter. "Introduction". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Topics in Algebraic Graph Theory. Encyclopedia of Mathematics and Its Applications. Vol. 102. Cambridge University Press. p. 6. ISBN 0-521-80197-4.

[bondy-murty-3] 1 2 3 Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. Elsevier. p. 58.

[:1-4] 1 2 3 4 Weisstein, Eric W. "Graph Join". mathworld.wolfram.com. Retrieved 2025-10-30.

[:0-5] 1 2 West, Douglas Brent (2001). Introduction to graph theory (2. ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0130144003.

[6] Gethner, Ellen (2018). "To the moon and beyond". In Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.). Graph theory—favorite conjectures and open problems. 2. Problem Books in Mathematics. Cham: Springer. pp. 115–133. ISBN 978-3-319-97684-6. MR 3930641.