Download Wolfram Notebook

A complete tripartite graph is the case of a complete k-partite graph. In other words, it is a tripartite graph (i.e., a set of graph vertices decomposed into three disjoint sets such that no two graph vertices within the same set are adjacent) such that every vertex of each set of graph vertices is adjacent to every vertex in the other two sets. If there are , , and graph vertices in the three sets, the complete tripartite graph (sometimes also called a complete trigraph) is denoted .

Special classes are summarized in the following table.

Some special cases are summarized in the following table, some of which are illustrated above.

The number of Hamiltonian cycles in the graph can be efficiently computed using a general complete k-partite graph recurrence (Horák and Tovarek 1979). A closed-form formula is also known (submitted as a problem, 2025).

Spectral comparisons ask which nonisomorphic graph on vertices is closest to in graph spectral distance. Jovanović et al. (2026) refuted two conjectures proposing as this minimizer for . Their counterexample is obtained from by adjoining a new graph vertex adjacent to every graph vertex in the part of size and to no others. For the taxicab metric and Euclidean metric on the ordered spectra, and . The second limit is for the squared distance, not the distance itself.

See also

Complete Bipartite Graph, Complete Graph, Complete k-Partite Graph, Cone Graph, Fan Graph, Graph Spectral Distance, k-Partite Graph

Explore with Wolfram|Alpha

References

--. Submitted problem to Amer. Math. Monthly. Feb. 2025.Chia, G. L. and Sim, K. A. "On the Skewness of the Join of Graphs." Disc. Appl. Math. 161, 2405-2409, 2013.Horák, P. and Tovarek, L. "On Hamiltonian Cycles of Complete -Partite Graphs." Math. Slovaca 29, 43-47, 1979.House of Graphs. Complete Tripartite Graphs. Triangle K_3, Diamond Graph, Octahedron K_{2,2,2}, K_2 + 3K_1, K_2 + 4K_1, and others.Jovanović, I. M.; Sedlar, J.; and Škrekovski, R. "Two Conjectures on the Cospectrality of Complete Tripartite Graphs Are False." 13 Oct 2026. https://arxiv.org/abs/2610.18636.

Referenced on Wolfram|Alpha

Complete Tripartite Graph

Cite this as:

Weisstein, Eric W. "Complete Tripartite Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CompleteTripartiteGraph.html

Subject classifications