กราฟ Graceful คือกราฟ G ที่มี p จุด และ q เส้นซึ่งเราสามารถกำหนดค่าที่ต่างกันให้กับจุดทุกจุดในกราฟด้วยจำนวนเต็มในเซต 0,1,2,...,q โดยที่น้ำหนักของเส้น e ในกราฟ G เท่ากับ |i - j| เมื่อ i และ j เป็นค่าที่ถูกกำหนดให้กับจุดปลายของ e จึงเกิดความสงสัยว่ากราฟพื้นฐานที่รู้จัก เช่น วิถี, กราฟไบพาไทต์ เป็นกราฟ Graceful หรือไม่