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

ปัญหาที่พอล เออร์โดส ตั้งขึ้น ซึ่งรู้จักกันในชื่อปัญหาระยะทางหน่วยถามถึงจำนวนคู่ระยะทางหน่วยสูงสุดที่เป็นไปได้ที่กำหนดโดยจุดในระนาบยุคลิด หรือกล่าวอีกนัยหนึ่งคือ ถามถึงจำนวนขอบสูงสุดในกราฟระยะทางหน่วยบนจุดยอด ขอบเขตบนที่ดีที่สุดที่ทราบคือขอบเขตล่างที่ดีที่สุดที่ทราบคือ(สำหรับค่า ที่มากพอ) จำนวนสีที่จำเป็นในการระบายสีกราฟระยะทางหน่วย T ก็ยังไม่เป็นที่ทราบเช่นกัน ในปัญหาแฮดวิเกอร์-เนลสัน ที่เทียบเท่ากัน สำหรับระนาบ กราฟระยะทางหน่วยบางกราฟต้องการห้าสี และกราฟระยะทางหน่วยทุกกราฟสามารถระบายสีได้ด้วยเจ็ดสี สำหรับทุกจำนวนพีชคณิตจะมีกราฟระยะทางหน่วยที่มีจุดยอดสองจุดที่ต้องอยู่ห่างกันตามทฤษฎีบทเบ็คแมน-ควาร์ลส์การแปลงระนาบเพียงอย่างเดียวที่รักษากราฟระยะทางหน่วยทั้งหมดไว้ได้คือไอโซเมตรี ${\displaystyle n}$${\displaystyle n}$${\displaystyle O(n^{4/3}).}$${\displaystyle \โอเมก้า (n^{1.014})}$${\displaystyle n)}$${\displaystyle \alpha ,}$${\displaystyle \alpha .}$

การสร้างกราฟระยะทางหน่วยอย่างมีประสิทธิภาพนั้นเป็นไปได้ หากกำหนดจุดต่างๆ มาให้ การค้นหาระยะทางหน่วยทั้งหมดมีประโยชน์ในการจับคู่รูปแบบซึ่งอาจเป็นขั้นตอนแรกในการค้นหาสำเนาที่เหมือนกันของรูปแบบขนาดใหญ่ อย่างไรก็ตาม การพิจารณาว่ากราฟที่กำหนดสามารถแสดงเป็นกราฟระยะทางหน่วยได้หรือไม่นั้นเป็นปัญหาNP-hardและโดยเฉพาะอย่างยิ่งเป็นปัญหาสมบูรณ์สำหรับทฤษฎีการมีอยู่ของจำนวนจริง

กราฟPetersenเป็นกราฟระยะทางหน่วย^{[ 1 ]}

กราฟ โมเบียส-แคนเตอร์เป็นกราฟย่อยของกราฟระยะทางหน่วย

กราฟระยะทางหน่วยสำหรับเซตของจุดในระนาบคือกราฟแบบไม่มีทิศทางที่มีจุดเหล่านั้นเป็นจุดยอดโดยมีขอบระหว่างจุดยอดสองจุดก็ต่อเมื่อระยะทางแบบยุคลิด ของจุดยอดทั้งสอง เท่ากับหนึ่งพอดี กราฟนามธรรมเรียกว่ากราฟระยะทางหน่วยได้ก็ต่อเมื่อสามารถหาตำแหน่งที่แตกต่างกันในระนาบสำหรับจุดยอดของกราฟนั้นได้ โดยที่ขอบของกราฟมีความยาวหนึ่งหน่วย และจุดยอดที่ไม่ติดกันทุกคู่มีระยะทางไม่เป็นหนึ่งหน่วย เมื่อเป็นไปได้เช่นนี้ กราฟนามธรรมจะสมสัณฐานกับกราฟระยะทางหน่วยของตำแหน่งที่เลือกไว้ หรืออีกทางหนึ่ง บางแหล่งข้อมูลใช้คำจำกัดความที่กว้างกว่า โดยอนุญาตให้จุดยอดที่ไม่ติดกันมีระยะทางเป็นหน่วยได้ กราฟที่ได้จะเป็นกราฟย่อยของกราฟระยะทางหน่วย (ตามที่กำหนดไว้ที่นี่) ^{[ 2 ]}ในกรณีที่คำศัพท์อาจกำกวม กราฟที่ไม่มีขอบจะต้องอยู่ห่างกันเป็นระยะทางไม่เป็นหนึ่งหน่วย อาจเรียกว่ากราฟระยะทางหน่วยที่เข้มงวด^{[ 3 ]}หรือกราฟระยะทางหน่วยที่ซื่อสัตย์^{[ 2 ]}กราฟย่อยของกราฟระยะทางหน่วยเทียบเท่ากับกราฟที่สามารถวาดในระนาบโดยใช้ความยาวขอบเพียงเส้นเดียว^{[ 4 ]}เพื่อความกระชับ บทความนี้จะเรียกสิ่งเหล่านี้ว่า "กราฟระยะทางหน่วยที่ไม่เข้มงวด"

กราฟระยะทางหน่วยไม่ควรสับสนกับกราฟดิสก์หน่วยซึ่งเชื่อมต่อจุดสองจุดเมื่อระยะทางน้อยกว่าหรือเท่ากับหนึ่ง และมักใช้ในการจำลองเครือข่ายการสื่อสารไร้สาย^{[ 5 ]}

กราฟสมบูรณ์บนจุดยอดสองจุดเป็นกราฟระยะทางหน่วย เช่นเดียวกับกราฟสมบูรณ์บนจุดยอดสามจุด ( กราฟสามเหลี่ยม ) แต่ไม่ใช่กราฟสมบูรณ์บนจุดยอดสี่จุด^{[ 3 ]}เมื่อขยายกราฟสามเหลี่ยมกราฟวงจรทุกกราฟเป็นกราฟระยะทางหน่วย ซึ่งสร้างขึ้นโดยรูปหลายเหลี่ยมปกติ^{[ 4 ]}กราฟระยะทางหน่วยจำกัดสองกราฟที่เชื่อมต่อกันที่จุดยอดร่วมจุดเดียว จะให้กราฟระยะทางหน่วยอีกกราฟหนึ่ง เนื่องจากกราฟหนึ่งสามารถหมุนเทียบกับอีกกราฟหนึ่งเพื่อหลีกเลี่ยงระยะทางหน่วยเพิ่มเติมที่ไม่ต้องการ^{[ 6 ]}ด้วยการเชื่อมต่อกราฟเช่นนี้ต้นไม้หรือกราฟกระบองเพชร จำกัดทุกกราฟ จึงสามารถสร้างขึ้นเป็นกราฟระยะทางหน่วยได้^{[ 7 ]}

กราฟไฮเปอร์คิวบ์ มีจุดยอด 16 จุด และระยะทางหน่วย 32 หน่วย${\displaystyle Q_{4}}$

กราฟแฮมมิง มีจุดยอด 27 จุด และระยะทางหน่วย 81 ระยะทาง${\displaystyle H(3,3)}$

ผลคูณคาร์ทีเซียน ของกราฟระยะทางหน่วย ใดๆจะสร้างกราฟระยะทางหน่วยอีกกราฟหนึ่ง อย่างไรก็ตาม สิ่งเดียวกันนี้ไม่เป็นจริงสำหรับผลคูณกราฟทั่วไปอื่นๆ ตัวอย่างเช่นผลคูณแบบเข้มของกราฟเมื่อนำไปใช้กับกราฟที่ไม่ว่างเปล่าสองกราฟใดๆ จะสร้างกราฟย่อยสมบูรณ์ที่มีสี่จุดยอด ซึ่งไม่ใช่กราฟระยะทางหน่วย ผลคูณคาร์ทีเซียนของกราฟเส้นทางจะสร้างกราฟกริดที่มีมิติใดๆ ผลคูณคาร์ทีเซียนของกราฟสมบูรณ์บนสองจุดยอดคือกราฟไฮเปอร์คิวบ์^{[ 8 ]}และผลคูณคาร์ทีเซียนของกราฟสามเหลี่ยมคือกราฟแฮมมิ ง^{[ 9 ]}${\displaystyle H(d,3)}$

กราฟเฉพาะอื่นๆ ที่เป็นกราฟระยะทางหน่วย ได้แก่^กราฟ Petersen [ ^{10 ]} กราฟHeawood ^{[ 11 ]} กราฟล้อ ( กราฟ ล้อเพียงกราฟเดียวที่เป็นกราฟระยะทางหน่วย) ^{[ 3 ]} และ กราฟ แกนหมุน Moserและกราฟ Golomb (กราฟระยะทางหน่วย 4 สีขนาดเล็ก) ^{[ 12 ]}กราฟ Petersen ทั่วไป ทั้งหมดเช่นกราฟ Möbius–Kantorที่แสดงไว้ เป็นกราฟระยะทางหน่วยที่ไม่เข้มงวด^{[ 13 ]}${\displaystyle W_{7}}$

กราฟไม้ขีดไฟเป็นกรณีพิเศษของกราฟระยะทางหน่วย ซึ่งไม่มีขอบตัดกัน กราฟไม้ขีดไฟทุกกราฟเป็นกราฟระนาบ^{[ 14 ]}แต่กราฟระยะทางหน่วยที่เป็นระนาบบางกราฟ (เช่น แกนหมุนของโมเซอร์) มีจุดตัดในทุกการแสดงเป็นกราฟระยะทางหน่วย นอกจากนี้ ในบริบทของกราฟระยะทางหน่วย ควรใช้คำว่า 'ระนาบ' ด้วยความระมัดระวัง เนื่องจากผู้เขียนบางคนใช้คำนี้เพื่ออ้างถึงระนาบที่กำหนดระยะทางหน่วย แทนที่จะหมายถึงการห้ามจุดตัด^{[ 3 ]}กราฟเหรียญเป็นกรณีพิเศษยิ่งกว่าของกราฟระยะทางหน่วยและกราฟไม้ขีดไฟ ซึ่งจุดยอดทุกคู่ที่ไม่ติดกันจะอยู่ห่างกันมากกว่าหนึ่งหน่วย^{[ 14 ]}

ปัญหาที่ยังแก้ไม่ได้ในวิชาคณิตศาสตร์

จุดชุดหนึ่งสามารถกำหนดระยะทางหน่วยได้กี่แบบ?${\displaystyle n}$

ปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์ยังมีอีกมากมาย

Paul Erdős  ( 1946 ) ตั้งปัญหาในการประมาณว่าจะมีจุดกี่คู่ในเซตของจุดที่สามารถอยู่ห่างกันเป็นระยะทางหนึ่งหน่วยได้ ในแง่ของทฤษฎีกราฟ คำถามนี้ถามว่ากราฟระยะทางหนึ่งหน่วยจะมีความหนาแน่นได้มากแค่ไหน และผลงานตีพิมพ์ของ Erdős เกี่ยวกับคำถามนี้เป็นหนึ่งในผลงานแรกๆ ใน ทฤษฎี กราฟสุดขั้ว^{[ 15 ]}${\displaystyle n}$

ให้จำนวนนี้เป็นA การสร้างด้วยกราฟไฮเปอร์คิวบ์และกราฟแฮมมิงแสดงให้เห็นว่าโดยการพิจารณาจุดในตารางสี่เหลี่ยมที่มีระยะห่างที่เลือกอย่างระมัดระวัง เออร์ดอสพบขอบล่างที่ปรับปรุงแล้วสำหรับค่าคงที่บางค่าบทความนี้ยังได้กำหนดขอบบนด้วย${\displaystyle g(n).}$${\displaystyle g(n)=\โอเมก้า (n\log n)}$${\displaystyle g(n)>n^{1+c/\log \log n},}$${\displaystyle c>0.}$${\displaystyle g(n)<n^{3/2}.}$

เนื่องจากขอบเขตบนคือในขณะที่ขอบเขตล่างถูกครอบงำโดยค่าคงที่ ใดๆ Erdős จึงตั้งข้อสันนิษฐานว่า สำหรับค่าคงที่ใดๆสำหรับการพิสูจน์หรือการหักล้างข้อสันนิษฐานนี้ เขาเสนอรางวัล 300 ดอลลาร์^{[ 16 ]}จากนั้นเพิ่มเป็น 500 ดอลลาร์^{[ 17 ]}ในเดือนพฤษภาคม 2026 ข้อสันนิษฐานนี้ถูกหักล้างโดยแบบจำลอง AI โดยOpenAIโดยการสร้างสำหรับ ซึ่งโดยที่การสร้างนี้ใช้ทฤษฎีจำนวนพีชคณิตโดยเฉพาะอย่างยิ่งวิธีหอคอยฟิลด์คลาส^{[ 18 ] [ 19 ]} ขอบเขตได้รับการปรับปรุงอย่างรวดเร็วเป็นโดยWill Sawin [ ^{20 ] นี่}เป็นตัวอย่างของการเชื่อมโยงต่างๆ ของกราฟระยะทางกับจำนวนพีชคณิตและความแข็งแกร่ง ผลที่ตามมาคือ ข้อสันนิษฐานนี้หักล้างข้อสันนิษฐานของ Erdős และFishburn (Erdős เสนอ 500 ดอลลาร์สำหรับการพิสูจน์ แต่เพียง 50 ดอลลาร์สำหรับการหักล้าง) ^{[ 21 ] [ 22 ]}${\displaystyle n^{3/2},}$${\displaystyle n^{1+c/\log \log n}}$${\displaystyle n^{1+\เอปไซลอน }}$${\displaystyle \epsilon >0,}$${\displaystyle \epsilon >0,}$${\displaystyle g(n)=O(n^{1+\epsilon }).}$${\displaystyle g(n)\geq \Omega (n^{1+\epsilon })}$${\displaystyle \epsilon \approx 6.24\times 10^{-38}}$${\displaystyle \epsilon >0.014}$

ในอีกทิศทางหนึ่ง ขอบเขตบนที่เป็นที่รู้จักดีที่สุดสำหรับปัญหานี้คือขอบเขตนี้สามารถมองได้ว่าเป็นการนับเหตุการณ์ระหว่างจุดและวงกลมหน่วย และมีความเกี่ยวข้องอย่างใกล้ชิดกับความไม่เท่าเทียมกันของจำนวนจุดตัดและทฤษฎีบท Szemerédi–Trotterเกี่ยวกับเหตุการณ์ระหว่างจุดและเส้นตรง^{[ 23 ]}$${\displaystyle g(n)\leq {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

ในปี พ.ศ. 2492 Erdős และLeo Moserได้ตั้งคำถามเกี่ยวกับกรณีพิเศษของปัญหานี้สำหรับจุดยอดของรูปหลายเหลี่ยมนูนในกรณีนี้ จำนวนระยะทางหน่วยสูงสุดคือ^{[ 24 ]}มีเพียงขอบเขตล่างเชิงเส้นเท่านั้นที่ทราบ^{[ 25 ]}${\displaystyle n\log _{2}n+4n.}$${\displaystyle 2n-7,}$

สำหรับค่าเล็กๆจำนวนขอบสูงสุดที่เป็นไปได้ที่แน่นอนเป็นที่ทราบกันดี สำหรับจำนวนขอบเหล่านี้คือ: ^{[ 26 ]}${\displaystyle n}$${\displaystyle n=2,3,4,\dots }$

ปัญหาสามารถขยายไปสู่บรรทัดฐานยุคลิดบน^{[ 27 ]}สำหรับ Erdős คู่พิสูจน์แล้วว่า^{[ 28 ]}สำหรับ Erdős คี่ และ Pachพิสูจน์แล้วว่า^{[ 29 ]}กรณีของยังคงเป็นกรณีเปิด ผลลัพธ์ที่ดีที่สุดคือสำหรับขอบล่าง และสำหรับขอบบนสำหรับ^{[ 30 ] ใดๆ}${\displaystyle \mathbb {R} ^{3},\mathbb {R} ^{4},\dots .}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle d\geq 4,}$${\displaystyle g(n)={\tfrac {1}{2}}(1-1/\lfloor d/2\rfloor )n^{2}+\Theta (n).}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle d\geq 5,}$${\displaystyle g(n)={\tfrac {1}{2}}(1-1/\lfloor d/2\rfloor )n^{2}+\Theta (n^{4/3}).}$${\displaystyle \mathbb {R} ^{3}}$${\displaystyle g(n)\geq \Omega (n^{4/3}\log \log n)}$${\displaystyle g(n)\leq O(n^{295/197+\epsilon })}$${\displaystyle \epsilon .}$

ปัญหาสามารถขยายไปสู่บรรทัดฐานใดๆ บนบรรทัดฐานใดๆ ที่ กำหนดบรรทัดฐานให้ตามนั้น ปัญหาได้รับการแก้ไขใน กรณี ทั่วไปโดยเฉพาะอย่างยิ่ง เมื่อกำหนดจำนวนเต็มใดๆสำหรับบรรทัดฐานเกือบทั้งหมดนั่นคือ เซตของบรรทัดฐานที่ละเมิดเงื่อนไขนี้มีจำนวนน้อยในเซตของบรรทัดฐานทั้งหมดของที่ถือว่าเป็นปริภูมิเมตริกซึ่งวัดโดยระยะทาง Hausdorffระหว่างลูกบอลหน่วยบรรทัดฐาน ในแง่นี้ บรรทัดฐานยุคลิดบนมีความพิเศษ เนื่องจากอยู่ในเซตที่น้อยนี้^{[ 31 ] [ 27 ]}${\displaystyle \mathbb {R} ^{d}.}$${\displaystyle \|\cdot \|,}$${\displaystyle g_{\|\cdot \|}(n)}$${\displaystyle d\geq 2,}$${\displaystyle \|\cdot \|,}$$${\displaystyle {\frac {d-1-o(1)}{2}}n\log _{2}n\leq g_{\|\cdot \|}(n)\leq {\frac {d}{2}}n\log _{2}n}$$${\displaystyle \mathbb {R} ^{d},}$${\displaystyle \mathbb {R} ^{2}}$

ในอีกทิศทางหนึ่ง ( Valtr 2005 ) ได้สร้างเมตริกที่คล้ายกับเมตริกยุคลิด แต่ซึ่งชี้ให้เห็นว่าสำหรับคำถามเดิม การปรับปรุงเมตริกดังกล่าวจะใช้คุณสมบัติที่ละเอียดอ่อนบางอย่างของบรรทัดฐานยุคลิดโดยเฉพาะ^{[ 32 ]}${\displaystyle \mathbb {R} ^{2}}$${\displaystyle g(n)\geq \โอเมก้า (n^{4/3}),}$${\displaystyle g(n)\leq O(n^{4/3})}$

ถ้ากราฟที่กำหนดไม่ใช่กราฟระยะทางหน่วยแบบไม่เข้มงวด ซูเปอร์กราฟใดๆของกราฟนั้นก็จะไม่ใช่กราฟระยะทางหน่วยแบบเข้มงวดเช่นกัน แนวคิดที่คล้ายกันนี้ใช้ได้กับกราฟระยะทางหน่วยแบบเข้มงวด แต่ใช้แนวคิดของซับกราฟเหนี่ยวนำซึ่งเป็นซับกราฟที่เกิดจากขอบทั้งหมดระหว่างคู่ของจุดยอดในเซตย่อยของจุดยอดที่กำหนด ถ้ากราฟไม่ใช่กราฟระยะทางหน่วยแบบเข้มงวด ซูเปอร์กราฟอื่นๆที่มีกราฟเหนี่ยวนำเป็นกราฟนั้นก็จะไม่ใช่กราฟระยะทางหน่วยแบบเข้มงวดเช่นกัน เนื่องจากความสัมพันธ์เหล่านี้ระหว่างซับกราฟหรือซูเปอร์กราฟของมันเป็นกราฟระยะทางหน่วยหรือไม่ จึงเป็นไปได้ที่จะอธิบายกราฟระยะทางหน่วยโดยใช้ซับกราฟต้องห้าม ซับกราฟเหล่านี้เป็นกราฟขั้นต่ำที่ไม่ใช่กราฟระยะทางหน่วยของประเภทที่กำหนด สามารถใช้เพื่อตรวจสอบว่ากราฟที่กำหนดเป็นกราฟระยะทางหน่วยหรือไม่ ไม่ว่าจะเป็นประเภทใดก็ตาม กราฟเป็นกราฟระยะทางหน่วยแบบไม่เข้มงวดก็ต่อเมื่อไม่ใช่ซูเปอร์กราฟของกราฟต้องห้ามสำหรับกราฟระยะทางหน่วยแบบไม่เข้มงวดกราฟเป็นกราฟระยะทางหน่วยแบบเข้มงวดก็ต่อเมื่อไม่ใช่ซูเปอร์กราฟเหนี่ยวนำของกราฟต้องห้ามสำหรับกราฟระยะทางหน่วยแบบเข้มงวด^{[ 8 ]}${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

สำหรับกราฟระยะทางหน่วยทั้งแบบไม่เข้มงวดและแบบเข้มงวด กราฟต้องห้ามจะรวมถึงกราฟสมบูรณ์และกราฟสองส่วนสมบูรณ์ด้วย สำหรับ กราฟระยะทางหน่วย ไม่ว่าจะวางจุดยอดด้านสองจุดยอดของกราฟนี้ไว้ที่ใด ก็จะมีตำแหน่งที่อยู่ห่างจากจุดยอดเหล่านั้นไม่เกินสองตำแหน่งเพื่อวางจุดยอดอีกสามจุด ดังนั้นจึงเป็นไปไม่ได้ที่จะวางจุดยอดทั้งสามจุดไว้ที่จุดที่แตกต่างกัน^{[ 8 ]}นี่เป็นกราฟต้องห้ามเพียงสองกราฟสำหรับกราฟระยะทางหน่วยแบบไม่เข้มงวดที่มีจุดยอดไม่เกินห้าจุด มีกราฟต้องห้ามหกกราฟที่มีจุดยอดไม่เกินเจ็ดจุด^{[ 6 ]}และ 74 กราฟที่มีจุดยอดไม่เกินเก้าจุด เนื่องจากการเชื่อมต่อกราฟระยะทางหน่วยสองกราฟ (หรือกราฟย่อยของกราฟเหล่านั้น) ที่จุดยอดหนึ่งจุดจะทำให้เกิดกราฟระยะทางหน่วยแบบเข้มงวด (หรือแบบไม่เข้มงวด) ดังนั้นกราฟต้องห้ามทุกกราฟจึงเป็นกราฟเชื่อมต่อ สองจุด ซึ่งไม่สามารถสร้างขึ้นได้ด้วยกระบวนการเชื่อมต่อนี้^{[ 33 ]}${\displaystyle K_{4}}$${\displaystyle K_{2,3}}$${\displaystyle K_{2,3}}$

กราฟ วงล้อ สามารถรับรู้ได้ว่าเป็นกราฟระยะทางหน่วยที่เข้มงวด โดยมีจุดยอดหกจุดก่อตัวเป็นรูปหกเหลี่ยมปกติ หน่วย และจุดที่เจ็ดอยู่ที่ศูนย์กลางของรูปหกเหลี่ยม การลบขอบหนึ่งออกจากจุดยอดตรงกลางจะสร้างกราฟย่อยที่มีขอบยาวหน่วยอยู่ แต่ไม่ใช่กราฟระยะทางหน่วยที่เข้มงวด การวางจุดยอดเป็นรูปหกเหลี่ยมปกติเป็นวิธีเดียว ( จนถึงความสอดคล้องกัน ) ในการวางจุดยอดในตำแหน่งที่แตกต่างกันโดยที่จุดยอดที่อยู่ติดกันมีระยะห่างหนึ่งหน่วย และการวางตำแหน่งนี้ยังทำให้จุดปลายทั้งสองของขอบที่หายไปมีระยะห่างหนึ่งหน่วยด้วย ดังนั้นจึงเป็นกราฟต้องห้ามสำหรับกราฟระยะทางหน่วยที่เข้มงวด^{[ 34 ]}แต่ไม่ใช่หนึ่งในหกกราฟต้องห้ามสำหรับกราฟระยะทางหน่วยที่ไม่เข้มงวด ตัวอย่างอื่นๆ ของกราฟที่ไม่ใช่กราฟระยะทางหน่วยที่เข้มงวดแต่ไม่ใช่กราฟระยะทางหน่วยที่เข้มงวด ได้แก่ กราฟที่เกิดจากการลบขอบด้านนอกออกจากและกราฟหกจุดยอดที่เกิดจากปริซึมสามเหลี่ยมโดยการลบขอบออกจากสามเหลี่ยมรูปหนึ่ง^{[ 33 ]}${\displaystyle W_{7}}$${\displaystyle W_{7}}$

สำหรับจำนวนพีชคณิต ทุกจำนวน สามารถสร้างกราฟระยะทางหน่วยได้โดยที่จุดยอดบางคู่มีระยะทางเท่ากันในการแสดงระยะทางหน่วยทั้งหมดของ[ ^{35 ] ผลลัพธ์} นี้บ่งบอกถึง ทฤษฎีบท Beckman–Quarles เวอร์ชันจำกัด: สำหรับจุดสองจุดใดๆและที่มีระยะทางเท่ากัน จะมีกราฟระยะทางหน่วยแบบแข็งเกร็ง จำกัดที่มี และอยู่ ซึ่งการแปลงระนาบใดๆ ที่รักษาระยะทางหน่วยในกราฟนี้ จะรักษาระยะทางระหว่างและ ด้วย[ ^{36 ] ทฤษฎีบท} Beckman–Quarles ฉบับเต็มระบุว่า การแปลงระนาบยุคลิด (หรือปริภูมิยุคลิดมิติสูงกว่า) เพียงอย่างเดียวที่รักษาระยะทางหน่วย คือไอโซเมตรี เทียบเท่ากับกราฟระยะทางหน่วยอนันต์ที่สร้างขึ้นโดยจุดทั้งหมดในระนาบ การแปลงกราฟอัตโนมัติทั้งหมดจะรักษาระยะทางทั้งหมดในระนาบ ไม่ใช่แค่ระยะทางหน่วย^{[ 37 ]}${\displaystyle \alpha }$${\displaystyle G}$${\displaystyle \alpha }$${\displaystyle G}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \alpha }$${\displaystyle p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q}$

ถ้าเป็นจำนวนพีชคณิตที่มีค่าสัมบูรณ์ เท่ากับ 1 ซึ่งไม่ใช่รากของเอกภาพการรวมกันของจำนวนเต็มของกำลังของจะก่อให้เกิดกลุ่มย่อยที่สร้างขึ้นอย่างจำกัดของกลุ่มบวกของจำนวนเชิงซ้อนซึ่งกราฟระยะทางหน่วยมีดีกรี อนันต์ ตัวอย่างเช่นสามารถเลือกให้เป็นหนึ่งในสองรากเชิงซ้อนของพหุนามทำให้เกิดกราฟระยะทางหน่วยดีกรีอนันต์ที่มีตัวสร้างสี่ตัว^{[ 38 ]}${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

ปัญหา Hadwiger–Nelson เกี่ยวข้องกับจำนวนสีของกราฟระยะทางหน่วย และโดยเฉพาะอย่างยิ่งกราฟระยะทางหน่วยอนันต์ที่สร้างขึ้นจากจุดทั้งหมดของระนาบยุคลิด ตามทฤษฎีบท de Bruijn–Erdősซึ่งถือว่าสัจพจน์ของการเลือกสิ่งนี้เทียบเท่ากับการถามถึงจำนวนสีที่มากที่สุดของกราฟระยะทางหน่วยจำกัด มีกราฟระยะทางหน่วยที่ต้องการห้าสีในการระบายสีที่เหมาะสมใดๆ^{[ 39 ]}และกราฟระยะทางหน่วยทั้งหมดสามารถระบายสีได้ด้วยสีไม่เกินเจ็ดสี^{[ 40 ]}

เพื่อตอบคำถามอีกข้อของ Paul Erdős เป็นไปได้ที่กราฟระยะทางหน่วยที่ไม่มีสามเหลี่ยม จะต้องใช้สี่สี ^{[ 41 ]}

จำนวนกราฟระยะทางหน่วยที่เข้มงวดบนจุดยอดที่มีป้ายกำกับมีค่าสูงสุด^{[ 2 ]} ตามที่แสดงโดยใช้สัญกรณ์บิ๊กโอและสัญกรณ์ลิตเติลโอ ${\displaystyle n\geq 4}$$${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

นิยามของกราฟระยะทางหน่วยสามารถขยายไปสู่ปริภูมิยุคลิด มิติสูงใดๆ ได้อย่างเป็นธรรมชาติ ในสามมิติ กราฟระยะทางหน่วยของจุดจะมีขอบอย่างมากที่สุด โดยที่เป็นฟังก์ชันที่เติบโตช้ามากซึ่งเกี่ยวข้องกับฟังก์ชัน Ackermannผกผัน^{[ 42 ]}ผลลัพธ์นี้นำไปสู่ขอบเขตที่คล้ายกันสำหรับจำนวนขอบของกราฟเพื่อนบ้านสัมพัทธ์สาม มิติ ^{[ 43 ]}ในสี่มิติหรือมากกว่านั้นกราฟสองส่วนสมบูรณ์ ใดๆ ก็ เป็นกราฟระยะทางหน่วย ซึ่งเกิดขึ้นจากการวางจุดบนวงกลมสองวงที่ตั้งฉากกันโดยมีจุดศูนย์กลางร่วมกัน ดังนั้นกราฟระยะทางหน่วยจึงสามารถเป็นกราฟหนาแน่นได้^{[ 7 ]}สูตรการนับสำหรับกราฟระยะทางหน่วยจะขยายไปสู่มิติที่สูงขึ้น และแสดงให้เห็นว่าในมิติสี่หรือมากกว่านั้น จำนวนกราฟระยะทางหน่วยที่เข้มงวดจะมีขนาดใหญ่กว่าจำนวนกราฟย่อยของกราฟระยะทางหน่วยมาก^{[ 2 ]}${\displaystyle n}$${\displaystyle n^{3/2}\beta (n)}$${\displaystyle \beta }$

กราฟจำกัดใดๆ ก็สามารถฝังเป็นกราฟระยะทางหน่วยในมิติที่สูงเพียงพอได้ กราฟบางกราฟอาจต้องการมิติที่แตกต่างกันมากสำหรับการฝังเป็นกราฟระยะทางหน่วยที่ไม่เข้มงวดและกราฟระยะทางหน่วยที่เข้มงวด ตัวอย่างเช่น กราฟมงกุฎที่มีจุดยอด -จุดอาจถูกฝังในสี่มิติเป็นกราฟระยะทางหน่วยที่ไม่เข้มงวด (นั่นคือ ขอบทั้งหมดของกราฟมีความยาวหนึ่งหน่วย) อย่างไรก็ตาม ต้องใช้อย่างน้อยมิติในการฝังเป็นกราฟระยะทางหน่วยที่เข้มงวด เพื่อให้ขอบของกราฟเป็นคู่ระยะทางหน่วยเพียงคู่เดียว^{[ 44 ]}มิติที่จำเป็นในการสร้างกราฟใดๆ ให้เป็นกราฟระยะทางหน่วยที่เข้มงวดนั้นมีค่าสูงสุดเป็นสองเท่าของดีกรีสูงสุด^{[ 45 ]}${\displaystyle 2n}$${\displaystyle n-2}$

การสร้างกราฟระยะทางหน่วยจากจุดต่างๆ เป็นขั้นตอนสำคัญสำหรับอัลกอริทึมอื่นๆ ในการค้นหาสำเนาที่สอดคล้องกันของรูปแบบบางอย่างในชุดจุดที่ใหญ่กว่า อัลกอริทึมเหล่านี้ใช้การสร้างนี้เพื่อค้นหาตำแหน่งที่เป็นไปได้ซึ่งมีระยะทางหนึ่งในรูปแบบอยู่ จากนั้นใช้วิธีการอื่นๆ เพื่อทดสอบส่วนที่เหลือของรูปแบบสำหรับผู้สมัครแต่ละราย^{[ 46 ]}วิธีการของMatoušek (1993)สามารถนำมาใช้กับปัญหานี้ได้^{[ 46 ]}ทำให้ได้อัลกอริทึมสำหรับการค้นหากราฟระยะทางหน่วยของชุดจุดระนาบในเวลาโดยที่ เป็น ฟังก์ชันลอการิทึมแบบวนซ้ำที่เติบโตช้า^{[ 47 ]}${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$${\displaystyle \log ^{*}}$

การทดสอบว่ากราฟที่กำหนดให้เป็นกราฟระยะทางหน่วย (แบบเข้มงวดหรือไม่เข้มงวด) ในระนาบนั้นเป็นปัญหาNP-hard —และโดยเฉพาะอย่างยิ่งเป็นปัญหา NP-complete สำหรับทฤษฎีการมีอยู่ของจำนวนจริง— ก็เป็นปัญหา NP-complete เช่นกัน ^{[ 48 ]}นอกจากนี้ การ พิจารณาว่ากราฟระยะทางหน่วยในระนาบมีวัฏจักรแฮมิลโทเนียน หรือไม่ ก็เป็นปัญหา NP-complete เช่นกัน แม้ว่าจุดยอดทั้งหมดของกราฟจะมีพิกัดจำนวนเต็มที่ทราบแล้วก็ตาม^{[ 49 ]}

• Venkatasubramanian, Suresh, "ปัญหาที่ 39: ระยะห่างระหว่างเซตของจุดในR ²และR ³ " , โครงการปัญหาเปิด
• ไวส์สไตน์, เอริค ดับเบิลยู. , "กราฟระยะทางหน่วย" , MathWorld