The graph disjoint union of graphs and is obtained by replacing them, if necessary, by isomorphic copies having disjoint vertex sets, and then taking their graph union (Harary 1994, p. 21; Gross and Yellen 2006, p. 85). Thus vertices and edges from the two input graphs remain distinct even when their original vertex labels coincide, and no edges are added between the two copies.

The operation is commonly denoted (Gromada 2022; Bucić and Sudakov 2023, p. 544). The alternate notation is also used (Georgakopoulos 2025). Knuth (2025, p. 23) instead denotes it . The graph disjoint union of copies of a graph is commonly denoted (Harary 1994, p. 21).

The Wolfram Language function GraphDisjointUnion[g1, g2, ...] treats vertices and edges in the input graphs as distinct regardless of their labels.

See also

Disjoint Union, Graph Join, Graph Sum, Graph Union

Explore with Wolfram|Alpha

References

Bucić, M. and Sudakov, B. "Large Independent Sets from Local Considerations." Combinatorica 43, 505-546, 2023. https://doi.org/10.1007/s00493-023-00023-w.Georgakopoulos, A. "On Graph Classes with Minor-Universal Elements." J. Combin. Th., Ser. B 170, 56-81, 2025. https://doi.org/10.1016/j.jctb.2024.09.001.Gromada, D. "Group-Theoretical Graph Categories." J. Algebraic Combin. 55, 591-627, 2022. https://doi.org/10.1007/s10801-021-01063-5.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 21, 1994.Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4, Fascicle 7: Constraint Satisfaction. Boston, MA: Addison-Wesley, p. 23, 2025.

Referenced on Wolfram|Alpha

Graph Disjoint Union

Cite this as:

Weisstein, Eric W. "Graph Disjoint Union." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphDisjointUnion.html

Subject classifications