# Definition:Complete Graph

Jump to navigation
Jump to search

*This page is about Complete Graph. For other uses, see Complete.*

## Definition

Let $G = \struct {V, E}$ 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

- Complete Graph is Hamiltonian for Order Greater than 2
- Complement of Complete Graph is Edgeless Graph

This page or section has statements made on it that ought to be extracted and proved in a Theorem page.In particular: All the below ought to be extracted into theoremsYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed.To discuss this page in more detail, feel free to use the talk page. |

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

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

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**complete graph** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**complete graph**