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 theorems You 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
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): complete graph
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.