Complete Graphs

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