Definition:Complete Graph

Definition

Let $G = \left({V, E}\right)$ be a simple graph such that every vertices is adjacent to every other vertex.

Then $G$ is called complete.

A complete graph of order $p$ is $p-1$-regular and is denoted $K_p$.

Examples

The first five complete graphs are shown below:

Basic Properties

• $K_n$ is Hamiltonian for all $n \ge 3$, from Ore's Theorem or trivially, by inspection.

• $K_1$ is the edgeless graph $N_1$, and also the path graph $P_1$.

• $K_2$ is the path graph $P_2$, and also the complete bipartite graph $K_{1, 1}$.

• $K_3$ is the cycle graph $C_3$, and is also called a triangle.

• $K_4$ is the graph of the tetrahedron.

• The complement of $K_n$ is the edgeless graph $N_n$.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.1$