# Definition:Complete Graph

Jump to navigation
Jump to search

## Contents

## Definition

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

Then $G$ is called **complete**.

The **complete graph** of order $p$ is denoted $K_p$.

## Examples

The first five complete graphs are shown below:

## Also see

- $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$.

- Results about
**complete graphs**can be found here.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 2.1$: The Degree of a Vertex