# 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^{} |