Misalkan graf G adalah sebuah graf sederhana tak berarah dengan himpunan simpul V dan himpunan busur E, di mana 𝑛=|𝑉| dan 𝑚=|𝐺| berturut-turut menyatakan banyaknya simpul dan busur graf G. Pelabelan graceful adalah suatu pemetaan injektif f yang memetakan himpunan simpul ke {0,1,2…m} yang menginduksi pemetaan bijektif 𝜆 yang memetakan himpunan busur ke {1,2,…m}, dimana label busur tersebut merupakan selisih dari label simpul yang dihubungkan oleh busur tersebut. Graf yang mempunyai pelabelan graceful disebut graf graceful.Untuk graf G dengan m busur dan pemetaan 𝑓:𝑉(𝐺)→ 0,1,2,…𝑚 maka matriks adjacency diperumum adalah matriks 𝐴 𝑚+1 ×(𝑚+1) dengan entri 𝑎𝑖𝑗 adalah 1 apabila terdepat busur vivj yang menghubungkan simpul vi berlabel i dan simpul vj berlabel j. Matriks adjacency diperumum akan digunakan untuk mengkonstruksi graf graceful baru dari graf yang telah diketahui graceful. Konstruksi dilakukan dengan tiga cara. Pertama adalah dengan pemindahan entri matriks adjacency. Kedua adalah dengan pengabungan matriks adjacency dan penggantian entri diagonal tertentu. Ketiga adalah penggabungan matriks adjacency dan penambahan baris dan kolom. Hasil lain yang diperoleh adalah kelas graf graceful baru: 𝑃𝑝△𝐶𝑛 dan 𝐾1⋄𝑝𝐺.