# Join (graph theory)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Join_(graph_theory)
> Markdown URL: https://mediated.wiki/source/Join_(graph_theory).md
> Source: https://en.wikipedia.org/wiki/Join_(graph_theory)
> Source revision: 1321118675
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Operation that combines two graphs}}

[[File:Join operation on graphs C4 and K4.svg|thumb|Join operation on graphs [{{mvar|C{{sub|4}}}}](/source/cycle_graph) (blue) and [{{mvar|K{{sub|4}}}}](/source/complete_graph) (red).]]

In [graph theory](/source/graph_theory), the '''join''' operation is a [graph operation](/source/Graph_operations) that combines two graphs by connecting every vertex of one graph to every vertex of the other.<ref name="bollobas">{{cite book|first=Béla |last=Bollobás |author-link=Béla Bollobás |title=Modern Graph Theory |publisher=Springer |series=[Graduate Texts in Mathematics](/source/Graduate_Texts_in_Mathematics) |year=1998 |isbn=0-387-98491-7 |page=7}}</ref><ref name="TAGT">{{cite book|title=Topics in Algebraic Graph Theory |editor-first1=Lowell W. |editor-last1=Beineke |editor-first2=Robin J. |editor-last2=Wilson |publisher=Cambridge University Press |series=Encyclopedia of Mathematics and Its Applications |volume=102 |chapter=Introduction |first1=Lowell |last1=Beineke |author-link1=L. W. Beineke |first2=Robin |last2=Wilson |author-link2=Robin Wilson (mathematician) |first3=Peter |last3=Cameron |author-link3=Peter Cameron (mathematician) |isbn=0-521-80197-4 |page=6}}</ref><ref name=bondy-murty>{{cite book|title=Graph Theory with Applications|first1=J. A.|last1=Bondy|first2=U. S. R.|last2=Murty|publisher=Elsevier|year=1976|page=58}}</ref> The join of two graphs <math>G_1</math> and <math>G_2</math> is denoted <math>G_1 + G_2</math>,<ref name="bollobas"/><ref name="TAGT"/> <math>G_1\vee G_2</math>,<ref name=bondy-murty/> or <math>G_1 \nabla G_2</math>.

== Definition ==

Let <math>G_1 = (V_1, E_1)</math> and <math>G_2 = (V_2, E_2)</math> be two [disjoint graphs](/source/Glossary_of_graph_theory). The '''join''' <math>G_1 + G_2</math> is a graph with:<ref name="bollobas"/><ref name="TAGT"/><ref name=bondy-murty/>

* Vertex set: <math>V(G_1 + G_2) = V_1 \cup V_2</math>
* Edge set: <math>E(G_1 + G_2) = E_1 \cup E_2 \cup \{uv \mid u \in V_1, v \in V_2\}</math>

In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in <math>G_1</math> to every vertex in <math>G_2</math>.

== Examples ==

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

;[Complete bipartite graph](/source/Complete_bipartite_graph)
: <math>K_{m,n} = \overline{K}_m + \overline{K}_n</math> (join of two [independent sets](/source/Independent_set_(graph_theory))).
;[Wheel graph](/source/Wheel_graph)
: <math>W_n = C_n + K_1</math> (join of a [cycle graph](/source/cycle_graph) and a single vertex).<ref name=":1">{{Cite web |last=Weisstein |first=Eric W. |title=Graph Join |url=https://mathworld.wolfram.com/GraphJoin.html |access-date=2025-10-30 |website=mathworld.wolfram.com |language=en}}</ref>
;[Star graph](/source/Star_(graph_theory))
: <math>S_{n+1} = \overline{K}_n + K_1</math> (join of a <math>n</math> vertex [empty graph](/source/Null_graph) and a single vertex).<ref name=":1" />
;[Fan graph](/source/Fan_graph)
: <math>F_{m,n} = P_n + \overline{K}_m</math> (join of a [path graph](/source/path_graph) with a empty graph).<ref name=":1" />
;[Complete graph](/source/Complete_graph)
: <math>K_n = K_m + K_{n-m}</math> (join of two complete graphs whose orders sum to <math>n</math>).
;[Cograph](/source/Cograph)
: Cographs are formed by repeated join and [disjoint union](/source/Disjoint_union_of_graphs) operations starting from single vertices.
;[Windmill graph](/source/Windmill_graph)
:<math>D_n^{(m)} = mK_{n-1} + K_1 </math> (join of $m$ copies of the complete graph on <math>n-1</math> vertices with a single vertex).<ref name=":1" />

== Properties ==

=== Basic properties ===
The join operation is [commutative](/source/commutative) for unlabeled graphs: <math>G_1 + G_2 \cong G_2 + G_1</math>.

If <math>G_1</math> has <math>p_1</math> vertices and <math>q_1</math> edges, and <math>G_2</math> has <math>p_2</math> vertices and <math>q_2</math> edges, then <math>G_1 + G_2</math> has <math>p_1 + p_2</math> vertices and <math>q_1 + q_2 + p_1 p_2</math> edges. If <math>p_1>0</math> and <math>p_2>0</math> then <math>G_1 + G_2</math> is [connected](/source/Connectivity_(graph_theory)) (<math>K_{p_1,p_2}</math> is a subgraph).<ref name=":0">{{cite book |last1=West |first1=Douglas Brent |title=Introduction to graph theory |date=2001 |publisher=Prentice Hall |location=Upper Saddle River, NJ |isbn=978-0130144003 |edition=2.}}</ref>

=== Chromatic number ===
The [chromatic number](/source/chromatic_number) of the join satisfies: 

:<math>\chi(G_1 + G_2) = \chi(G_1) + \chi(G_2)</math>.

[[File:Sulanke Earth-Moon map.svg|thumb|The join of a 5-cycle and a 6-clique and its representation as an [Earth–Moon map](/source/Earth%E2%80%93Moon_problem)]]
This property holds because vertices from <math>G_1</math> and <math>G_2</math> 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](/source/Earth%E2%80%93Moon_problem) of coloring graphs of [thickness](/source/Thickness_(graph_theory)) two. Sulanke observed that the join <math>C_5+K_6</math> is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.<ref>{{cite book
 | last = Gethner | first = Ellen | author-link = Ellen Gethner
 | editor1-last = Gera | editor1-first = Ralucca
 | editor2-last = Haynes | editor2-first = Teresa W.
 | editor3-last = Hedetniemi | editor3-first = Stephen T.
 | contribution = To the moon and beyond
 | isbn = 978-3-319-97684-6
 | location = Cham
 | mr = 3930641
 | pages = 115–133
 | publisher = Springer
 | series = Problem Books in Mathematics
 | title = Graph theory—favorite conjectures and open problems. 2
 | year = 2018}}</ref>

<math>G_1 + G_2</math> is [color critical](/source/Critical_graph) if and only if <math>G_1</math> and <math>G_2</math> are both color critical.<ref name=":0" />

==See also==
*[Disjoint union of graphs](/source/Disjoint_union_of_graphs)
*[Graph minor](/source/Graph_minor)
*[Join (topology)](/source/Join_(topology))

== References ==
{{reflist}}

== External links ==
* {{MathWorld|title=Graph Join|urlname=GraphJoin}}

Category:Graph operations
Category:Graph theory

---
Adapted from the Wikipedia article [Join (graph theory)](https://en.wikipedia.org/wiki/Join_(graph_theory)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Join_(graph_theory)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.