Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

complete graph




A connected graph in which exactly one edge connects each pair of vertices. A complete graph with n vertices, denoted Kn, 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 Kn has degree n-1; therefore Kn 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