Chuyên Đề Bài toán:Tìm đường đi ngắn nhất-Lý thuyết đồ thị

Trong một đồ thị đơn giản phẳng, liên thông bất kỳ có n đỉnh, m cạnh (m>2) và f mặt. khi ấy ta có
3f/2<mn-6
MôMrgan: Mọi bản đồ đều có thể tô bằng 4 màu sao cho 2 nước nằm kề nhau phải được tô bằng 2 màu khác nhau
(1976 với sự trợ giúp của máy tính IBM đã chứng minh là đúng)
Giả sử G là đồ thị đơn không có định hướng có n đỉnh và m cạnh. Nếu m>(n.n+6-3n)/2 thì G là 1 đồ thị Hamilton .