Ta nhắc lại đn đỉnh tách: một đỉnh $v $ của đồ thị phẳng liên thông $G $ gọi là
đỉnh tách nếu $(G-v) $ không liên thông (ta đồng nhất $G $ với thể hiện hình học của nó, tức là xem nó như một tập hợp trong mp).
Bài toán: Cho $G $ là đồ thị phẳng liên thông không có đỉnh tách thỏa mãn hai điều kiên:
1) Mỗi đỉnh của nó là đầu mút của bốn cung
2) Tồn tại một cung nối hai đỉnh,gọi là $v_1,\ v_2 $, mà nếu ta xóa phần trong cung đó (tức là ko xóa $v_1,\ v_2 $) thì nhận được
đồ thị mới có đỉnh tách.
Chứng minh khi đó nếu với $G $ ta không xóa gì cả mà chỉ đồng nhất $v_1,\ v_2 $ thì đồ thị mới nhận được
sẽ không có đỉnh tách.
PS: Việc đồng nhất hai đỉnh $v_1,\ v_2 $ sẽ thu đc đồ thị mới như sau: Bỏ đi một trong hai đỉnh, chẳng hạn là $v_1 $. Xóa cung nối $v_1,\ v_2 $ và dựng thêm một cung từ $v_2 $ vào chính nó. Các cung nối các đỉnh khác $v_1,\ v_2 $ giữ nguyên. Các cung nối một đỉnh khác với $v_2 $ cũng giữ nguyên. Các cung nối một đỉnh khác với
$v_1 $ bị xóa, thay vào đó dựng 1 cung nối đỉnh đó với
$v_2 $.
Mình đang rất cần lời giải, mong ai đó trên 4rum giúp đỡ
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]