Simpul-simpul dalam suatu graf tidak selalu memiliki sisi di antaranya. Jika kita menambahkan semua sisi yang mungkin, graf yang dihasilkan disebut lengkap. Artinya, suatu graf lengkap jika setiap pasangan simpul dihubungkan oleh sebuah sisi. Karena suatu graf sepenuhnya ditentukan oleh simpul mana yang bertetangga dengan simpul lainnya, hanya ada satu graf lengkap dengan banyak simpul tertentu. Kita memberi graf-graf tersebut nama khusus: \(K_n\) adalah graf lengkap dengan \(n\) simpul.