complete graph

The complete graph with $n$ vertices, denoted $K_n$, contains all possible edges; that is, any two vertices are adjacent.

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

The number of edges in $K_n$ is the $n-1$th triangular number. Every vertex in $K_n$ has degree $n-1$; therefore $K_n$ has an Euler circuit if and only if $n$ is odd. A complete graph always has a Hamiltonian path, and the chromatic number of $K_n$ 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	complete
Synonym	clique
Related topic	Tournament