Bài này chính là chứng minh đồ thị 2 phía đầy đủ $K_{3,3}$ không phải là đồ thị phẳng.
Lời giải
Ta sẽ chứng minh bằng phản chứng.
Giả sử đồ thị $K_{3,3}$ là đồ thị phẳng.
Áp dụng công thức Euler cho đồ thị phẳng ta có $f=e-v+2=9-6+2=5$ với $f$ là số mặt của đồ thị, $e$ là số cạnh và $v$ là số đỉnh.
Tiếp theo ta sẽ chứng minh mỗi mặt của một đồ thị 2 phía phẳng cần sử dụng ít nhất 4 cạnh.
Thật vậy, gọi 2 tập đỉnh của $K_{3,3}$ là $A$ và $B$. Một mặt cần sử dụng ít nhất 3 cạnh, tuy nhiên 3 cạnh không cắt nhau (do đang giả sử là đồ thị phẳng) và đều là 3 cạnh nối 1 đỉnh tập $A$ đến 1 đỉnh tập $B$ thì không thể tạo thành tam giác được (đoạn này vẽ hình ra sẽ dễ hiểu hơn
), vậy nên một mặt cần sử dụng ít nhất 4 cạnh. Mà một cạnh thì là chung của 2 mặt vậy nên ta có bất đẳng thức là $4f \leq 2e$ hay $5=f \leq \frac{9}{2}$ (mâu thuẫn)
Ta có đpcm.
Các khái niệm được sử dụng
Đồ thị 2 phía : Đồ thị có 2 tập đỉnh $A$ và $B$, tất cả các cạnh đều là nối 2 đỉnh thuộc 2 tập khác nhau
Đồ thị 2 phía đầy đủ : Đồ thị 2 phía mà giữa 2 đỉnh bất kì thuộc 2 tập khác nhau thì đều có cạnh nối
Đồ thị phẳng : đồ thị không có 2 cạnh nào cắt nhau
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]