[hahahaha4]

Định lý 4: Định lý về đồ thị 2 phần.
Một đồ thị là 2 phần nếu và chỉ nếu không có chu trình sơ cấp độ dài lẻ

Đồ thị 2 phần là đồ thị mà ta có thể phân chia các đỉnh của nó thành hai tập hợp,mỗi tập hợp gồm các đỉnh độc lập với nhau.

Chứng minh:

+) Điều kiện cần: Nếu đồ thị là 2 phần.Một chu trình sẽ đi qua các đỉnh của của mỗi tập đỉnh độc lập 1 cách luân phiên nhau do đó chỉ qua lại đỉnh đầu tiên sau 1 số chẵn lần hay đồ thị có chu trình độ dài chẵn
+) Điều kiện đủ.Giả sử đồ thị $G$ không có chu trình đồ thị lẻ.Xét đỉnh có bậc lớn nhất trong $G$.Giả sử đó là đỉnh $A$.Chia tập đỉnh của $G$ thành 2 phần: phần $M$ chứa đỉnh $A$ và tất cả các đỉnh kề với $A$ và phần $N$ gồm các đỉnh còn lại.Đỉnh $A$ sẽ không được nối với các đỉnh thuộc tập $N$.Khi đó đưa đỉnh $A$ từ $M$ sang $N$.Xét trong tập $N$ đỉnh có bậc lớn nhất.Giả sử là $A_1$.(Dĩ nhiên bậc của nó nhỏ hơn $A$).Nếu $A_1$ nối với các đỉnh kề của $A$ thì các đỉnh kề của $A_1$ sẽ không được nối với bất kì đỉnh nào kề với $A$ nếu không ta sẽ có 1 chu trình độ dài lẻ.Khi đó ta thực hiện công đoạn chuyển các đỉnh kề của $A_1$ sang M.Còn nếu $A_1$ không được nối với bất kì đỉnh kề nào của $A$ ta chuyển $A_1$ sang $M$.Thực hiện liên tiếp quá trình này.Do số đỉnh là hữu hạn và số bậc giảm dần nên quá trình sẽ dừng lại.Ta được đồ thị hai phần

Chứng minh của mình.Mọi người cho ý kiến nhé.Rất thích cái topic này
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]