Complete Graphs
Table of Contents

Complete Graphs

Definition: A graph $G = (V(G), E(G))$ is said to be Complete if every vertex in the graph is joined to each other by exactly one edge. That is, a complete graph is always a simple graph since loops and multiple edges are not allowed.

We denote complete graphs on $n$-vertices by $K_n$. Here is some examples of complete graphs when $n = 1, 2, 3, 4$:


Notice that the degree of all vertices of a complete graph is $n-1$. You can verify this with the graphs $K_1$, $K_2$, $K_3$ and $K_4$ above and $\frac{n(n-1)}{2}$ edges as a consequence of The Handshaking Lemma.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License