complete graph

The complete graphMathworldPlanetmath with n vertices, denoted Kn, contains all possible edges; that is, any two vertices are adjacent.

The complete graph of 4 vertices, or K4 looks like this:

The number of edges in Kn is the n-1th triangular numberMathworldPlanetmath. Every vertex in Kn has degree n-1; therefore Kn has an Euler circuit if and only if n is odd. A complete graph always has a Hamiltonian pathMathworldPlanetmath, and the chromatic numberMathworldPlanetmath of Kn is always n.

Title complete graph
Canonical name CompleteGraph
Date of creation 2013-03-22 12:16:57
Last modified on 2013-03-22 12:16:57
Owner vampyr (22)
Last modified by vampyr (22)
Numerical id 10
Author vampyr (22)
Entry type Definition
Classification msc 05C99
Synonym completePlanetmathPlanetmath
Synonym clique
Related topic TournamentMathworldPlanetmath