O par não ordenado $\{A,B\}$ é uma separação de $G$ se $A \cup B = V$ e $G$ não tem arestas entre $A \setminus B$ e $B \setminus A$. Claramente, o último é equivalente a dizer que $A \cap B$ separa $A$ de $B$.
Se ambos $A \setminus B$ e $B \setminus A$ são não vazios, dizemos que a separação é adequada. O número $|A \cap B|$ é a ordem da separação $\{A,B\}$, e os conjuntos A, B são seus lados.