ข้อสันนิษฐานการสร้างใหม่ของStanisław Ulam เป็นหนึ่งใน ปัญหาเปิดที่รู้จักกันดีที่สุดในทฤษฎีกราฟโดยใช้คำศัพท์ของFrank Harary ^{[ 1 ]}สามารถกล่าวได้ดังนี้: ถ้าGและHเป็นกราฟสองกราฟบนจุดยอดอย่างน้อยสามจุด และ ƒ เป็นฟังก์ชัน หนึ่งต่อหนึ่งทั่วถึง จากV ( G ) ไปยังV ( H ) โดยที่G \{ v } และH \{ƒ( v )} เป็นไอโซมอร์ฟิกกัน สำหรับจุดยอด vทั้งหมดในV ( G ) แล้วGและHจะเป็นไอโซมอร์ฟิกกัน

ในปี พ.ศ. 2507 Harary ^{[ 2 ]}ได้ขยายสมมติฐานการสร้างใหม่ไปยังกราฟทิศทางที่มีจุดยอดอย่างน้อยห้าจุด ซึ่งเรียกว่าสมมติฐานการสร้างใหม่ของไดกราฟ ผลลัพธ์มากมายที่สนับสนุนสมมติฐานการสร้างใหม่ของไดกราฟปรากฏขึ้นระหว่างปี พ.ศ. 2507 ถึง พ.ศ. 2519 อย่างไรก็ตาม สมมติฐานนี้ได้รับการพิสูจน์ว่าผิดเมื่อ PK Stockmeyer ค้นพบกลุ่มตัวอย่างค้านคู่ของไดกราฟ (รวมถึงทัวร์นาเมนต์ ) ที่มีลำดับขนาดใหญ่มาก หลายกลุ่มจำนวนอนันต์ ^{[ 3 ] [ 4 ] [ 5 ]}ความเป็นเท็จของสมมติฐานการสร้างใหม่ของไดกราฟทำให้เกิดความสงสัยเกี่ยวกับสมมติฐานการสร้างใหม่เอง Stockmeyer ถึงกับสังเกตว่า “บางทีความพยายามอย่างมากที่ใช้ในการพยายามพิสูจน์สมมติฐาน (การสร้างใหม่) ควรได้รับการถ่วงดุลด้วยความพยายามที่จริงจังมากขึ้นในการสร้างตัวอย่างค้าน” ^{[ 3 ]}

ในปี พ.ศ. 2522 Ramachandran ได้ฟื้นฟูสมมติฐานการสร้างไดกราฟขึ้นใหม่ในรูปแบบที่อ่อนกว่าเล็กน้อย เรียกว่าสมมติฐานการสร้างไดกราฟขึ้นใหม่ในไดกราฟ จำนวนส่วนโค้งที่เชื่อมจาก (หรือไปยัง) จุดยอดvเรียกว่าดีกรีขาออก (หรือดีกรีขาเข้า ) ของvและเขียนแทนด้วยod ( v ) (หรือid ( v )) สมมติฐานไดกราฟขึ้นใหม่สามารถระบุได้ดังนี้: ^{[ 6 ] [ 7 ]}

ถ้าDและEเป็นกราฟระบุทิศทางใดๆ และƒเป็นฟังก์ชันหนึ่งต่อหนึ่งทั่วถึงจากV ( D ) ไปยังV ( E ) โดยที่D { v } และE {ƒ( v )} เป็นไอโซมอร์ฟิกกัน และ ( od ( v ), id ( v ))  =  ( od (ƒ( v )), id (ƒ( v ))) สำหรับทุกvในV ( D ) แล้วDและEก็เป็นไอโซมอร์ฟิกกัน

ข้อสันนิษฐานการสร้างกราฟทิศทางใหม่จะลดรูปไปเป็นข้อสันนิษฐานการสร้างกราฟทิศทางในกรณีที่ไม่มีทิศทาง เพราะถ้ากราฟย่อยที่ลบจุดยอดทั้งหมดของกราฟสองกราฟเป็นไอโซมอร์ฟิกกันแล้ว จุดยอดที่สอดคล้องกันจะต้องมีดีกรีเท่ากัน ดังนั้น ข้อสันนิษฐานการสร้างกราฟทิศทางใหม่จึงแข็งแกร่งกว่าข้อสันนิษฐานการสร้างกราฟทิศทางเดิม แต่ก็อ่อนแอกว่าข้อสันนิษฐานการสร้างกราฟทิศทางที่ถูกหักล้างไปแล้ว มีการแสดงให้เห็นแล้วว่ากราฟทิศทางหลายตระกูลเป็นไปตามข้อสันนิษฐานการสร้างกราฟทิศทางใหม่ ซึ่งรวมถึงกราฟทิศทางทั้งหมดในคู่ตัวอย่างค้านที่ทราบกันดีของข้อสันนิษฐานการสร้างกราฟทิศทาง

• ไดกราฟทั้งหมด สามารถสร้างใหม่ได้แบบ Nหากไดกราฟทั้งหมดที่มีกราฟพื้นฐานที่เชื่อมต่อแบบ 2 สามารถสร้างใหม่ได้แบบN ^{[ 8 ]}
• ไดกราฟทั้งหมด สามารถสร้างใหม่ได้แบบ Nก็ต่อเมื่อไดกราฟประเภทใดประเภทหนึ่งต่อไปนี้ สามารถสร้างใหม่ได้แบบ Nโดยที่ diam( D ) และ radius( D ) ถูกกำหนดให้เป็นเส้นผ่านศูนย์กลางและรัศมีของกราฟพื้นฐานของD ^{[ 9 ]}
  1. ไดกราฟที่มี diam( D ) ≤ 2 หรือ diam( D ) = diam( D ^c ) = 3
  2. กราฟระบุทิศทางDที่มีกราฟพื้นฐานแบบ 2-เชื่อมต่อ และรัศมี( D ) ≤ 2

ณ ปี 2024 ยังไม่มีตัวอย่างค้านใด ๆ ที่ทราบสำหรับสมมติฐานการสร้างกราฟทิศทางใหม่นี้ สมมติฐานนี้จึงถูกเรียกว่าสมมติฐานการสร้างกราฟทิศทางที่เกี่ยวข้องกับดีกรี ด้วย เช่น กัน