Graph join G+H: take G∪H and add all edges from V(G) to V(H). |E(G+H)| = |E₁|+|E₂|+|V₁|·|V₂|. Examples: K_1+C_n = W_{n+1} (wheel). K_1+K_n = K_{n+1}. E_m+E_n = K_{m,n}. χ(G+H) = χ(G)+χ(H).
How to Use
Select G and H:
- |V|: |V₁|+|V₂|
- |E|: Formula
- Type: Wheel/complete/bipartite
Famous Joins
K₁+C_n = wheel W_{n+1}. K₁+P_n = fan graph. E_m+E_n = K_{m,n} (complete bipartite). K_m+K_n = K_{m+n}. The join always has diameter ≤ 2 (go through the bridge).
Chromatic Number
χ(G+H) = χ(G)+χ(H) always. Since every vertex of G is adjacent to every vertex of H, their color classes must be disjoint. This makes the join useful for constructing graphs with specific χ.
Step-by-Step Instructions
- 1Select G, H.
- 2Compute G+H.
- 3Count vertices/edges.
- 4Check χ.
- 5Identify structure.