A complete graph is a simple graph whose vertices are pairwise adjacent. In other words, there is an edge between every two vertices in the graph. In other words (version 2), every vertex in a complete graph has an edge to every other vertex in the graph.
A complete graph
vertices is usually denoted as Kn
. A complete graph is also sometimes called a clique
There are several variants of what is called a complete graph. There is the complete graph with loops where every vertex also has an edge going back to itself; and the complete directed graph where between every pair of vertices u and v there are two edges: one going from u to v, another going from v to u.
Another type of graph that is often discussed along with complete graphs is the complete bipartite graph. A complete bipartite graph is a bipartite graph such that for every vertex in one partite set, there is an edge to each vertex in the other partite set. That is, for every pair of vertices, there is an edge between them if and only if they belong to different partite sets. A complete bipartite graph with m vertices in one partite set and n vertices in the other partite set is often denoted as Km,n