# 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 CompleteGraph 2013-03-22 12:16:57 2013-03-22 12:16:57 vampyr (22) vampyr (22) 10 vampyr (22) Definition msc 05C99 complete clique Tournament