Upagraf adalah Graf yang dibentuk dari sebagian atau seluruh simpul dan sisi dari graf induknya. Sedangkan Cut Set adalah Himpunan sisi dalam graf yang, jika dihapus, menyebabkan graf menjadi tidak terhubung (terbagi menjadi dua atau lebih komponen yang terpisah).