Two Ways to Combine Graphs
Graph parameters can change predictably when two graphs are assembled into a larger graph. In a disjoint union, the two vertex sets remain separate, with no edges between them. In a join, every vertex of one graph is connected to every vertex of the other. These operations affect independent sets, cliques, and colorings in complementary ways: a union lets choices from both parts coexist, while a join forces choices or colors in the two parts to interact.
Throughout, graphs are finite and simple. An independent set is a set of vertices no two of which are adjacent; \(\alpha(G)\) is the largest size of such a set. A clique is a set of pairwise adjacent vertices; \(\omega(G)\) is the largest size of a clique. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; \(\chi(G)\) is the least number of colors in a proper coloring.
We use the convention that the graph with no vertices has \(\alpha=\omega=\chi=0\). A largest independent set or clique in that graph is empty, and it has a proper coloring with no colors. This convention also makes the formulas below valid when one or both graphs have no vertices. For a nonempty graph, at least one color is needed.
The Parameter Formulas
Proof. First consider \(G\cup H\). An independent set in the union restricts to an independent set in each graph, since the edges within each vertex set are unchanged. Its size is therefore at most \(\alpha(G)+\alpha(H)\). Conversely, take maximum independent sets in \(G\) and \(H\). Their union is independent in \(G\cup H\), because there are no edges between the two vertex sets. This proves the formula for \(\alpha\).
A clique in \(G\cup H\) cannot contain a vertex from each graph: there are no edges between the two vertex sets. Thus every nonempty clique lies entirely in one graph, and the largest possible size is \(\max\{\omega(G),\omega(H)\}\). This also holds if both graphs are empty, since the maximum is then \(0\).
Restricting any proper coloring of \(G\cup H\) to either graph gives a proper coloring there. Hence \(\chi(G\cup H)\) is at least both \(\chi(G)\) and \(\chi(H)\). For the reverse inequality, let \(k=\max\{\chi(G),\chi(H)\}\). Color each graph using colors from the same set of \(k\) colors. This is a proper coloring of the union because no edge joins the two graphs, so vertices in different graphs may reuse colors. If both graphs are empty, \(k=0\) and the empty coloring applies. Thus \(\chi(G\cup H)=k\).
Now consider \(G\vee H\). An independent set cannot contain a vertex from each graph, because every such pair is adjacent in the join. Therefore every independent set lies entirely in one graph, and the largest size is \(\max\{\alpha(G),\alpha(H)\}\). A clique in the join restricts to a clique in each graph. Its size is at most \(\omega(G)+\omega(H)\). Conversely, the union of a maximum clique in \(G\) and a maximum clique in \(H\) is a clique: the vertices are pairwise adjacent within each graph, and every cross pair is an added edge. This proves the formula for \(\omega\), including empty graphs.
For a proper coloring of \(G\vee H\), no color used on a vertex of \(G\) can be used on a vertex of \(H\), since every cross pair is adjacent. Restricting the coloring to each graph therefore requires at least \(\chi(G)\) colors for \(G\) and at least \(\chi(H)\) different colors for \(H\), with the two color sets disjoint. At least their sum is needed. Conversely, color \(G\) with \(\chi(G)\) colors and \(H\) with a separate set of \(\chi(H)\) colors. The result is proper within each graph and across every added edge. If a graph is empty, it contributes zero colors and no vertices; the same reasoning still applies. Hence \(\chi(G\vee H)=\chi(G)+\chi(H)\). \(\square\)
The pattern is worth remembering: for a union, independence numbers add, while clique and chromatic numbers take the larger value. For a join, clique and chromatic numbers add, while the independence number takes the larger value. The proofs rely on the defining difference between the operations—whether cross edges are absent or complete.
Worked Examples
Worked Example: A Disjoint Union of Two Complete Graphs
Let \(G\) have vertex set \(\{a,b\}\) and edge set \(\{ab\}\), and let \(H\) have vertex set \(\{c,d,e\}\) and edge set \(\{cd,ce,de\}\). Thus \(G=K_2\), \(H=K_3\), and the union has vertex set \(\{a,b,c,d,e\}\) and edge set \(\{ab,cd,ce,de\}\).
In \(K_2\), an independent set has at most one vertex, a clique can use both vertices, and the adjacent pair requires two colors. Hence \(\alpha(G)=1\), \(\omega(G)=2\), and \(\chi(G)=2\). In \(K_3\), each pair is adjacent, so an independent set has size at most one, the whole vertex set is a clique, and three different colors are required. Thus \(\alpha(H)=1\), \(\omega(H)=3\), and \(\chi(H)=3\).
The union formulas give \(\alpha(G\cup H)=1+1=2\), \(\omega(G\cup H)=\max\{2,3\}=3\), and \(\chi(G\cup H)=\max\{2,3\}=3\). For a direct check, \(\{a,c\}\) is independent, and no independent set can take more than one vertex from either complete component, so the maximum is \(2\). The vertices \(\{c,d,e\}\) form a triangle, so a clique of size \(3\) exists; no clique can use vertices from both components. Finally, colors \(1,2,3\) suffice: assign \(a\) color \(1\), \(b\) color \(2\), and \(c,d,e\) colors \(1,2,3\), respectively. The triangle forces at least three colors, confirming \(\chi=3\).
Worked Example: The Join of \(K_2\) and \(K_3\)
Let \(G\) have vertex set \(\{1,2\}\) and edge set \(\{12\}\). Let \(H\) have vertex set \(\{3,4,5\}\) and edge set \(\{34,35,45\}\). Their join has vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,34,35,45,13,14,15,23,24,25\}\): the first four edges are internal, and the other six are all cross edges.
As complete graphs, \(G\) has parameters \((\alpha,\omega,\chi)=(1,2,2)\), and \(H\) has parameters \((1,3,3)\). The join formulas give \(\alpha(G\vee H)=\max\{1,1\}=1\), \(\omega(G\vee H)=2+3=5\), and \(\chi(G\vee H)=2+3=5\).
Check: The listed edge set contains all \(\binom{5}{2}=5\cdot4/2=10\) possible pairs, so the join is \(K_5\). Every pair is adjacent; therefore an independent set has size at most \(1\), all five vertices form a clique, and every vertex needs its own color. These direct checks give \(\alpha=1\), \(\omega=5\), and \(\chi=5\), as predicted.
Worked Example: Joining Graphs That Are Not Complete
Let \(G\) have vertex set \(\{a,b,c\}\) and edge set \(\{bc\}\), and let \(H\) have vertex set \(\{d,e\}\) and no edges. Their join has vertex set \(\{a,b,c,d,e\}\) and edge set \(\{bc,ad,ae,bd,be,cd,ce\}\).
In \(G\), the set \(\{a,b\}\) is independent, while \(b,c\) form an edge. Thus \(\alpha(G)=2\) and \(\omega(G)=2\). Two colors suffice: give \(b\) color \(1\) and \(c\) color \(2\); \(a\), which is adjacent to neither, can also receive color \(1\). Since \(bc\) is an edge, one color cannot suffice, so \(\chi(G)=2\). In \(H\), both vertices can be taken in an independent set and can share one color; its largest clique has size \(1\). Hence \((\alpha(H),\omega(H),\chi(H))=(2,1,1)\).
The join formulas give \(\alpha= \max\{2,2\}=2\), \(\omega=2+1=3\), and \(\chi=2+1=3\). To check independence directly, any independent set using vertices from both sides would contain an adjacent cross pair, so it must lie in \(G\) or \(H\); each side has an independent set of size \(2\), and neither has a larger one. The clique \(\{b,c,d\}\) has size \(3\), and no larger clique is possible because a clique uses at most two vertices from \(G\) and at most one from the edgeless \(H\). For coloring, give \(a\) and \(b\) color \(1\), \(c\) color \(2\), and both \(d,e\) color \(3\). The listed cross edges have different-colored endpoints, and the only internal edge \(bc\) does too. The edge \(bc\) needs two colors within \(G\), and the vertices of \(H\) need a color unavailable in \(G\), so three colors are necessary.
A Common Mistake and Why the Formulas Matter
A tempting but incorrect rule is to use the maximum of the two chromatic numbers for a join, just as for a disjoint union. In the preceding example, that would give \(\max\{2,1\}=2\). But every vertex of \(H\) is adjacent to every vertex of \(G\), so the color used on \(H\) cannot be reused in \(G\). The correct calculation is \(\chi(G\vee H)=2+1=3\). Reusing colors is valid across a disjoint union precisely because there are no cross edges.
These identities are useful when a large graph is built from smaller pieces. If its construction is expressed in terms of unions and joins, the parameters can be calculated recursively from the component parameters. The formulas also provide a check on a proposed coloring or on a claimed largest independent set or clique: an answer that conflicts with the relevant operation formula cannot be correct.
| Operation | Independence number | Clique number | Chromatic number |
|---|---|---|---|
| Disjoint union \(G\cup H\) | \(\alpha(G)+\alpha(H)\) | \(\max\{\omega(G),\omega(H)\}\) | \(\max\{\chi(G),\chi(H)\}\) |
| Join \(G\vee H\) | \(\max\{\alpha(G),\alpha(H)\}\) | \(\omega(G)+\omega(H)\) | \(\chi(G)+\chi(H)\) |
Check Your Understanding
Use the definitions of union and join to justify each answer, rather than relying only on the table.
- Let \(G\) and \(H\) be vertex-disjoint copies of \(K_2\). Find \(\alpha\), \(\omega\), and \(\chi\) for \(G\cup H\).
- For the same two graphs, find \(\alpha\), \(\omega\), and \(\chi\) for \(G\vee H\).
- Explain why a clique in a disjoint union cannot use vertices from both graphs.
- Explain why a proper coloring of a join must use disjoint sets of colors on its two vertex sets.
- Check that the join formulas still hold when \(H\) has no vertices.