Đồ thị cạnh đơn vị

Đồ thị cạnh đơn vị (tiếng Anh: unit distance graph) là đồ thị mà ta có thể vẽ nó trong mặt phẳng Euclid với tất cả các cạnh có độ dài bằng một.

Một số đồ thị cạnh đơn vị:
Đồ thị chu trình
Đồ thị lưới
Đồ thị siêu khối
Đồ thị Heawood
Đồ thị Petersen
Đồ thị bánh xe 

Với đồ thị chu trình , ta có thể biểu diễn nó trên mặt phẳng Euclid dưới dạng đa giác đều có n cạnh, mỗi cạnh có độ dài một đơn vị.
Ta chứng minh quy nạp đồ thị siêu khối  là đồ thị cạnh đơn vị theo n.
n=1,  có dạng một đoạn thẳng độ dài bằng một.
n=2,  có dạng một hình thoi bất kì với độ dài cạnh bằng một.
Giả sử  là đồ thị cạnh đơn vị, ta chứng minh rằng  cũng là đồ thị cạnh đơn vị.
Thật vậy,  cấu trúc bởi hai đồ thị  với từng cặp đỉnh tương ứng của chúng được nối với nhau. Như vậy ta có thể vẽ  dưới dạng đồ thị cạnh đơn vị bằng cách sau:

vẽ một đồ thị  dưới dạng đồ thị cạnh đơn vị, rồi vị tự nó đi một khoảng cách đúng bằng một, được đồ thị , cuối cùng ta nối các đỉnh tương ứng của hai đồ thị này lại. Trong ví dụ minh họa sau, đồ thị cạnh đơn vị G2 được biểu diễn bằng cách tịnh tiến đồ thị cạnh đơn vị G1 một khoảng có độ dài một đơn vị. Trong hình vẽ mũi tên màu đỏ chỉ sự tịnh tiến.

Bài toán đếm số khoảng cách đơn vị 

Năm 1946, Paul Erdos đề ra bài toán cho tập n điểm bất kì, có nhiều nhất bao nhiêu điểm trong số chúng có khoảng cách bằng một đơn vị. Trong lý thuyết đồ thị, vấn đề này được phát biểu: một đồ thị cạnh đơn vị với n đỉnh có nhiều nhất bao nhiêu cạnh.

Đồ thị siêu khối  có  đỉnh và  cạnh. Đó là bằng chứng để củng cố giả thiết rằng một đồ thị cạnh đơn vị với n đỉnh, có ít nhất là:

cạnh.

Năm 1984, Joel Spencer, Endre Szemorédi và William Trotter đưa ra một cận dưới cho đáp số của bài toán trên là:
.

Chú thích

Liên kết ngoài 
.

Lý thuyết đồ thị
Vấn đề chưa được giải quyết trong toán học