## complete graphA connected graph in which exactly one edge connects each pair of vertices. A complete graph with n vertices, denoted K_{n},
has n(n - 1)/2 edges (i.e., the nth triangular
number), (n-1)! Hamilton
circuits, and a chromatic number of n. Every vertex in K_{n} has degree n-1;
therefore K_{n} has an Euler
circuit if and only if n is odd. In a weighted complete
graph, each edge has a number called a weight attached to it. Each
path then has a total weight, which is the sum of the weights of the edges
in the path. ## Related entry• traveling salesman problem## Related category• GRAPHS AND GRAPH THEORY | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |