Trong các sách, tùy theo ý của tác giả hoặc theo yêu cầu của chủ đề cụ thể mà từ "đồ thị" có thể hàm ý cho phép hoặc không cho phép khuyên hay đa cạnh. Nếu đồ thị không cho phép đa cạnh (và không cho phép khuyên nếu là đồ thị có hướng), đồ thị được gọi là đồ thị đơn. Mặt khác, nếu cho phép đa cạnh (và đôi khi cả khuyên), đồ thị được gọi là đa đồ thị. Đôi khi, từ giả đồ thị (pseudograph) còn được dùng để hàm ý cả đa cạnh và. | ĐÍNHLỶ Cho G là một đơn đồ thị liỀn thông có V đinh E cạnh Vriị E è 3. Nếu G phảng thì ta có bất đổng thức Eí3 V-2 4 CHỬNG MiNHt Hiển nhiên. ĐỊNH LÝ KURA TOWSKI I Một cách tổng quát việc khảo sát tinh chất phảng của một đi thị là một bài toán khỗng dễ. Định lỷ Kuratoivskì đưa ra một điều kiện dt cỏ và đủ để một đổ thị là phdng. I ĐINH NGHĨA I Nhác lại rằng đơn đồ thị đẩy đủ có n đỉnh được ký hiệu là V .X n n - 1 1 Kn và có cạnh. Dễ thấy K1 Ka K b Kf đểu phồng. Hơn nữa .thí dụ 4 đ trên chứng tỏ rằng Kn n è 5 khổng phảng. I Đồ thị lưỡng phân đầy đủ complete bipartite graph KflJ là 1 đơn đồ thị có m n đỉnh gồm m đỉnh bên trái vồ n đinh bên phải sao cho mỗi đỉnh bên trái đếu có cạnh nối đến mọi đỉnh bên phải. I Dễ thấy rằng Km n có mn cạnh. I K Do thí dụ 3 Kn . m n 3 không phẳng. Kết quả tổ 66 quát về tính chất phắng cùa đồ thị lường phân đầy H được nêu ở phần bài tập. Từ đồ thị Go cho trước ta xây dựng 1 đổ thi G theo cách sau Thêm vào Go cổc đỉnh mới và các cạnh mới đỉnh mới có thể nối với 1 đinh khác bằng 1 cạnh mái đỉnh mđi cũng có thể được đạt nằm trên 1 cạnh cũ và chia cạnh cù này thành 2 cạnh mới Ta nói rằng đồ thị G nhận được là có chứa cấu hình configuration Go. Ta đã biết rằng và Kfi không phẳng do đó hiển nhiên nếu một đồ thị có chứa cấu hình hoặc Kr thì nó không phảng. Điều dào lại cũng đúng và là khảng định của định lý Kuratowski ĐINH LÝ Kuratowakl phdn. nếu và chi nếu G khôns chứa cấu hình cũng như Kị. Phần chứng minh của định lý này khá phức tạp và sè Không trình bày ở đây. Độc giả cỏ thể tham khảo trong 1 Ta cổ thể dùng định lý Kuratowski để chứng minh 1 đồ thị là không phẳng. D Ta vè lại chúng như sau 67 1 nếu eị là cạnh biên của mặt fj m J 0 nếu 6ị không là cạnh biên của mặt fj Xét hàng thứ i. Vì cạnh e là cạnh biên củ nhiều nhất là 2 mặt nên tổng các phẩn t trên hàng này 2 1 F J Xmij s 2 j i 11 E F Ị Suy ra Xm j XSmy-2E 1 KisE Ỉ 1 j l lắjsF Lại xét cột thứ j. Vì mặt fj có ít nhất g cạạ biên nên tổng các phần .
