Đồ thị đầy đủ

Đồ thị đầy đủ

K7, Đồ thị đầy đủ có 7 đỉnh

số đỉnh: n

đường kính: 1

chu trình ngắn nhất: 3 nếu n ≥ 3

số cạnh: $\frac{n (n-1)}{2}$

kí hiệu: $K_n$

số đồ thị đẳng cấu: n! (Sn)

sắc số: n

số màu cạnh: n nếu n lẻ n-1 nếu n chẵn

spectral_gap = $\frac{n}{n-1}$

tính chất khác (n-1)-chính quy Đồ thị đối xứng Vertex-transitive Edge-transitive Strongly regular Integral

Đồ thị đầy đủ n đỉnh (tiếng Anh: complete graph), kí hiệu là $K_n$ (chữ K lấy từ tiếng Đức komplett), là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối.

Đồ thị $K_n$ có tất cả $n(n-1)/2$ cạnh. Nó là đồ thị đơn có nhiều cạnh nhất, đồng thời là đồ thị chính quy bậc n-1.

Ví dụ

Sau đây là danh sách và hình vẽ minh họa các đồ thị đầy đủ với số đỉnh từ 1 đến 12, cùng với số cạnh của chúng:

$K_1: 0$	$K_2: 1$	$K_3: 3$	$K_4: 6$
$K_5: 10$	$K_6: 15$	$K_7: 21$	$K_8: 28$
$K_9: 36$	$K_{10}: 45$	$K_{11}: 55$	$K_{12}: 66$