complete graphCompleteGraph2002-02-03 14:51:402002-05-27 15:22:50Definition% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands hereThe \emph{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:
\begin{center}
\includegraphics[scale=1.0]{k4.eps}
\end{center}
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$.