Tài liệu Số ramsey

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LƯU NGỌC HOÀN SỐ RAMSEY LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LƯU NGỌC HOÀN SỐ RAMSEY LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 Người hướng dẫn khoa học PGS.TS ĐÀM VĂN NHỈ THÁI NGUYÊN - 2015 Mục lục 1 Lý thyết đồ thị 1.1 1.2 1.3 6 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . 6 1.1.1 Đồ thị có hướng-Đồ thị vô hướng . . . . . . . . . 7 1.1.2 Hành trình, đường, chu trình, vết và mạch . . . . 10 1.1.3 Tính liên thông . . . . . . . . . . . . . . . . . . 14 1.1.4 Cây . . . . . . . . . . . . . . . . . . . . . . . . . 15 Một vài đồ thị đặc biệt . . . . . . . . . . . . . . . . . . 17 1.2.1 Đồ Thị Euler . . . . . . . . . . . . . . . . . . . . 17 1.2.2 Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 20 1.2.3 Đồ thị phẳng . . . . . . . . . . . . . . . . . . . . 22 Bài toán tô màu . . . . . . . . . . . . . . . . . . . . . . 25 1.3.1 Định lý bốn màu . . . . . . . . . . . . . . . . . 28 1.3.2 Tô màu đỉnh . . . . . . . . . . . . . . . . . . . . 29 1.3.3 Tô màu cạnh . . . . . . . . . . . . . . . . . . . . 30 1.3.4 Một vài bài toán vận dụng . . . . . . . . . . . . 30 2 Lý thuyết số Ramsey 2.1 33 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . 33 2.1.1 33 Nguyên lý lồng-chim . . . . . . . . . . . . . . . . 1 2 2.1.2 2.2 2.3 Một vài ví dụ ứng dụng . . . . . . . . . . . . . . 34 Khái niệm số Ramsey . . . . . . . . . . . . . . . . . . . 43 2.2.1 Bậc của đỉnh đồ thị . . . . . . . . . . . . . . . . 43 2.2.2 Số Ramsey và số chặn . . . . . . . . . . . . . . . 44 Một vài vận dụng . . . . . . . . . . . . . . . . . . . . . 52 2.3.1 Lý thuyết Ramsey trong Hình học . . . . . . . . 52 2.3.2 Tồn tại tam giác cùng màu . . . . . . . . . . . . 55 Lời nói đầu Bài toán sử dụng k màu để tô dãy số nguyên dương từ 1 đến n với n r−1 P ui đã đủ lớn đạt được dãy số cùng màu u1 , u2 , . . . , ur thỏa mãn ur = i=1 được I. Schur chứng minh vào năm 1916. Kết quả ấy được coi như viên gạch đầu tiên để dẫn đến định lý tổng quát được Frank Ramsey (19021930) chứng minh vào năm 1928. Kết quả của F. Ramsey với nhiều dạng mở rộng đã được ứng dụng không chỉ trong tổ hợp, đồ thị mà còn trong nhiều lĩnh vực khác chẳng hạn như Đại số, Hình học, Lý thuyết tập hợp,v.v... Vậy, bài toán đặt ra bởi F. Ramsey là gì? Ramsey xét bài toán chia tập hợp các cạnh của một đồ thị đầy đủ vào hai ngăn kéo bằng cách tô màu tất cả các cạnh đồ thị bởi hai màu đen và trắng. Ông khẳng định rằng, với mỗi cặp số nguyên dương p và q luôn tồn tại một số nguyên dương n sao cho với mọi cách tô các cạnh của đồ thị đầy đủ Kn bởi hai màu nói trên hoặc ta sẽ được một đồ thị đầy đủ Kp màu đen hoặc một đồ thị Kq màu trắng. Số nguyên nhỏ nhất n ở đây thường được ký hiệu bởi R(p, q) hoặc N (p, q). Chỉ trong những trường hợp đặc biệt hoặc giá trị nhỏ của số p, q ta có thể xác định chính xác giá trị N (p, q). Trong phần lớn các trường hợp khác ta chỉ có thể đưa ra cận trên hoặc cận dưới của N (p, q) mà thôi. Vấn đề tìm hiểu số Ramsey và vận dụng chúng trong công việc giảng 3 4 dạy, dạy học sinh chuyên toán và tự đào tạo là cần thiết. Do vậy, chúng tôi đã tập trung nghiên cứu lý thuyết đồ thị, nguyên lý Dirichlet và lý thuyết Ramsey trong luận văn của mình. Luận văn được chia ra làm 2 chương. Chương 1 tập trung trình bày về lý thuyết đồ thị gồm 3 mục. Mục 1.1 tập trung trình bày những khái niệm cơ bản của lý thuyết đồ thị. Mục 1.2 được dành để trình bày về những đồ thị hay tính chất đặc biệt như Đồ thị Euler, Đồ thị Hamilton. Mục 1.3 được dành để giới thiệu bài toán tô màu như: tô màu đỉnh, tô màu cạnh, tô màu đồ thị phẳng. Chương 2 tập trung trình bày về nguyên lý Dirichlet và lý thuyết Ramsey gồm 3 mục. Mục 2.1 tập trung trình bày nguyên lý Dirichlet và một vài ví dụ áp dụng. Đây là kỹ thuật để chứng minh một vài kết quả trong lý thuyết Ramsey. Mục 2.2 được dành để trình bày lý thuyết Ramsey. Chúng tôi cũng đã chứng minh một vài số chặn trên hoặc chặn dưới của số N (p, q). Mục 2.3 được dành để giới thiệu một vài mở rộng và xét bài toán Ramsey trong hình học. Tác giả xin bày tỏ lòng kính trọng và biết ơn chân thành đến người thầy, người hướng dẫn khoa học PGS. TS. Đàm Văn Nhỉ về sự giúp đỡ chu đáo, chỉ bảo tận tâm của thầy trong suốt quá trình hoàn thành luận văn. Trong quá trình học tập, nghiên cứu và hoàn thành bản luận văn, tác giả đã nhận được sự quan tâm giúp đỡ của các thầy, cô giáo, cán bộ nhân viên của Phòng đào tạo sau đại học và quan hệ quốc tế trường Đại học khoa học - Đại học Thái Nguyên. 5 Tác giả xin chân thành cảm ơn tác giả Kỷ yếu hội thảo khoa học các chuyên đề toán học bồi dưỡng học sinh giỏi khu vực duyên hải Nam Trung bộ và Tây nguyên và Bồi dưỡng học sinh giỏi Toán tổ hợp - rời rạc nhà xuất bản Đại học quốc gia Hà Nội. Thái Nguyên ngày 15 tháng 04 năm 2015 Lưu Ngọc Hoàn Chương 1 Lý thyết đồ thị 1.1 Các khái niệm cơ bản Lý thuyết đồ thị là một ngành khoa học đã được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ IIXX bởi nhà toán học Leonhard Euler, người Thụy sĩ. Ông là người đã sử dụng đồ thị để giải quyết nhiều bài toán nổi tiếng. Đồ thị, hoặc Graph, là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc tính và số các cạnh nối các cặp đỉnh của đồ thị. Nhiều bài toán thuộc lĩnh vực rất khác nhau có thể giải quyết được qua đồ thị. Chẳng hạn, có thể dùng đồ thị để biểu diễn sự cạnh tranh của các loài trong một môi trường sinh thái, để biểu diễn ai có ảnh hưởng lên ai trong một tổ chức nào đó, để biểu diễn các kết cục của cuộc thi đấu thể thao; cũng có thể dùng đồ thị để giải các bài toán như tính số các tổ hợp khác nhau của các chuyến bay giữa hai thành phố trong một mạng hàng không hoặc tìm số các màu cần thiết để tô các vùng khác nhau của một bản đồ. 6 7 1.1.1 Đồ thị có hướng-Đồ thị vô hướng Chúng ta bắt đầu lý thuyết đồ thị bằng một số khái niệm cơ bản sau: Định nghĩa 1.1.1. Một đồ thị có hướng G, (digraph), là một cặp có thứ tự G = (V, E), trong đó V là một tập và E là một tập con của tích Carte V × V , tức là E là một quan hệ hai ngôi trên V. Các phần tử thuộc V được gọi là các đỉnh, còn các phần tử thuộc E được gọi là các cung của đồ thị có hướng G. Nếu (a, b) ∈ E thì (a, b) còn được gọi là một cung của G với đỉnh đầu là a, đỉnh cuối b và hướng đi từ a tới b. Để có hình ảnh trực quan, người ta thường biểu diễn đồ thị có hướng G trên mặt phẳng như sau: Các đỉnh của G được biểu diễn bằng các vòng tròn nhỏ, còn các cung thì được biểu diễn bằng các đường cong nối đỉnh đầu với đỉnh cuối và có mũi tên hướng từ đỉnh đầu tới đỉnh cuối. Ví dụ 1.1.2. Cho đồ thị G = (V, E) với V = {a, b, c, d, e, f } và E = {(a, a), (a, b), (b, d), (d, b), (e, a)}. Khi đó G là một đồ thị có hướng. Giả sử G = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì ta nói các đỉnh a và b là liên thuộc với cung (a, b). Khi đó a và b cũng được gọi là kề nhau. Hai cung bất kỳ của G được gọi là kề nhau nếu chúng có đỉnh chung. Cùng dạng (a, a) với a ∈ V được gọi là khuyên. Đỉnh không liên thuộc với một cung nào được gọi là đỉnh độc lập của G; Số các đỉnh của G, tức là |V |, được gọi là cấp của G. Số các cung của G, tức là |E|, được gọi là cỡ của G. 8 Hình 1.1: Ví dụ một đồ thị có hướng. Định nghĩa 1.1.3. Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), trong đó V là một tập và E là tập với các phần tử là các đa tập lực lượng 2 trên V . Các phần tử thuộc V cũng được gọi là các đỉnh, còn các phần tử thuộc E được gọi là các cạnh của đồ thị vô hướng G. Nếu e = {a, b} là một cạnh của G thì a và b được gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc với e. Đôi khi ta thường ký hiệu cạnh {a, b} ngắn gọn là ab. Người ta cũng thường biểu diễn đồ thị vô hướng trên mặt phẳng tương tự như ta biểu diễn đồ thị có hướng: các đỉnh của đồ thị được biểu diễn bằng các vòng tròn nhỏ và các cạnh thì được biểu diễn bằng một đường cong nối các đỉnh của cạnh. Điểm khác biệt ở đây là không có mũi tên chỉ hướng trên các đường cong đó. Ví dụ 1.1.4. Cho đồ thị G = (V, E) với V = {a, b, c, d} và E = {(a, a), (a, b), (a, d), (b, c), (c, d)}. Khi đó G là một đồ thị vô hướng và 9 được biểu diễn bằng hình. Hình 1.2: Hình ví dụ một đồ thị vô hướng. Đồ thị có hướng ở được định nghĩa ở trên cũng thường được gọi là đơn đồ thị có hướng, lý do là vì với hai đỉnh a và b bất kỳ tồn tại duy nhất một cung với đỉnh đầu là a và đỉnh cuối là b. Với lý do tương tự, đồ thị vô hướng được định nghĩa ở trên cũng thường được gọi là đơn đồ thị vô hướng. Tuy nhiên, trong một số ứng dụng ta cần có nhiều cung với cùng đỉnh đầu và cùng đỉnh cuối hay cần nhiều cạnh cùng liên thuộc với hai đỉnh đã cho. Vì vậy người ta đưa ra khái niệm đa đồ thị có hướng và đa đồ thị vô hướng. Đôi khi có nhiều cạnh nối hai đỉnh trong một đồ thị. Chẳng hạn, trong một trường học mỗi người được xem như một đỉnh và đường nối giữa hai người là máy tính, điện thoại bàn, điện thoại di động, v.v.... Như vậy, thay cho đồ thị với mỗi cặp đỉnh chỉ một cạnh nối bằng một đồ thị với nhiều cạnh khác nhau nối hai đỉnh. 10 Định nghĩa 1.1.5. Một đa đồ thị G là một cặp có thứ tự G = (V, E) với tập V, tập các cạnh E và ánh xạ f từ E lên {{a, b}|a, b ∈ V, a 6= b}. Các cạnh e1 và e2 được gọi là song song hay cạnh bội nếu f (e1 ) = f (e2 ). Đa đồ thị có hướng cũng được định nghĩa tương tự và được biểu diễn trên mặt phẳng tương tự như đồ thị có hướng, trong đó các cung có cùng đỉnh đầu và đỉnh cuối phải được biểu diễn bằng các đường cong khác nhau. Tương tự, một đa đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một đa đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một đa tập với các phần tử đều là đa tập lực lượng 2 trên V , trong biểu diễn trên mặt phẳng của đa đồ thị vô hướng, các cạnh khác nhau nhưng có các đỉnh đầu mút như nhau phải được biểu diễn bằng các đường cong khác nhau. 1.1.2 Hành trình, đường, chu trình, vết và mạch Định nghĩa 1.1.6. Giả sử G = (V, E) là một đồ thị có hướng. Một hành trình có hướng trong G là một dãy v0 e1 v1 e2 v2 . . . en vn sao cho với mọi i = 0, 1, ..., n có vi ∈ V, còn với mọi i = 0, 1, 2, . . . , n có ei ∈ E và ei = (vi−1 , vi ). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn vn gọi là đỉnh cuối của hành trình có hướng trên. Tương tự, một hành trình vô hướng trong G là một dãy v0 e1 v1 e2 v2 ...en vn sao cho với mọi i = 0, 1, ..., n có vi ∈ V, còn với mọi i = 0, 1, 2, ..., n có ei ∈ E và hoặc ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn vn được gọi là đỉnh cuối của hành trình trên. Một hành trình (có hướng, vô hướng) được gọi là khép 11 kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Ví dụ 1.1.7. Giả sử G = (V, E) là một đồ thị có hướng (hình 6.2 trang 115). Khi đó (1) v1 e1 v2 e9 v6 e6 v5 e7 v2 e2 v3 là một hành trình có hướng với đỉnh đầu là v1 , đỉnh cuối là v3 và độ dài bằng 5. (2) v1 e1 v2 e7 v5 e4 v4 e3 v3 e2 v2 e7 v5 e5 v6 là một hành trình vô hướng với đỉnh đầu là v1 đỉnh cuối là v6 và độ dài là 7. (3) v2 e9 v6 e6 v5 e7 v2 là một hành trình có hướng khép kín. (4) v2 e7 v5 e5 v4 e3 v3 e2 v2 là một hành trình vô hướng khép kín. Hình 1.3: Dùng để minh họa cho hành trình trong đồ thị. Trong trường hợp hành trình có hướng, mỗi cung ei đều có đỉnh đầu là đỉnh đứng trước và đỉnh cuối là đỉnh đứng sau ei trong dãy, tức là nó 12 được xác định bởi chính hai đỉnh đó. Vì vậy người ta thường đơn giản gọi dãy các đỉnh v0 v1 v2 ...vn của G là hành trình có hướng trong G nếu với mọi i = 0, 1, ....n − 1, (vi , vi+1 ) là một cung của G. Tình huống sẽ hơi khác với trường hợp hành trình vô hướng. Nếu trong G, giữa hai đỉnh vi và vj có cả hai cung là e1 = (vi , vj ) và e2 = (vi , vj ) thì hai dãy con vi e1 vj và vi e2 vj là hai đoạn khác nhau trong hành trình. Vì thế, cung giữa vi và vj cần được chỉ ra cụ thể. Tuy nhiên nên trong G chỉ có một cung giữa vi và vj hoặc là (vi , vj ) (hoặc (vj , vi ) nhưng không đồng thời cả hai), thì cung giữa hai đỉnh đó cũng được xác định duy nhất trongG bởi vi và vj . Do đó để đơn giản ta cũng thay đoạn vi e1 vj với e1 = (vi , vj ) hay vi e2 vj với e2 = (vi , vj ) của hành trình bằng vi , vj . Một hành trình có hướng (tương ứng, vô hướng), trong đó các đỉnh đều khác nhau được gọi là một đường có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng), trong đó các cung đều khác nhau được gọi là một vết có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng ) khép kín, mà khi xóa đỉnh cuối thì trở thành một đường có hướng (tương ứng, vô hướng), được gọi là một chu trình có hướng (tương ứng, vô hướng) khép kín, trong đó các cung đều khác nhau, được gọi là một mạch có hướng (tương ứng, vô hướng). Trên đây ta đã đưa ra các định nghĩa của hành trình, đường, chu trình, vết và mạch (có hướng, vô hướng) trong đồ thị có hướng. Các 13 Hình 1.4: Đồ thị Petersen. khái niệm tương tự cũng có thể định nghĩa trong đồ thị vô hướng. Tuy nhiên, ta nhận xét thấy rằng trong đồ thị vô hướng giữa hai đỉnh bất kỳ có nhiều nhất là một cạnh. Vì thế, các khái niệm trên có thể định nghĩa trong đồ thị vô hướng đơn giản hơn như sau: Giả sử G = (V, E) là một đồ thị vô hướng. Một hành trình tất nhiên là vô hướng trong G là một dãy các đỉnh v0 v1 v2 ...vn sao cho ví dụ mọi i = 0, 1, 2, ...n − 1, và (vi , vi+1 ) là một cạnh của G. Các cạnh (vi vi+1 ), i = 0, 1, 2, ...n − 1, cũng được gọi là các cạnh của hành trình v0 v1 v2 ...vn . Khi đó n được gọi là độ dài, v0 được gọi là đỉnh đầu, còn vn gọi là đỉnh cuối của hành trình trên. Một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Một hành trình được gọi là một đường nếu các đỉnh của hành trình đó đều khác nhau. Một hành trình được gọi là vết nếu các cạnh của hành trình đó đều khác nhau. Một hành trình khép kín được gọi là chu trình, nếu nó có độ dài ít nhất là 3 và khi xóa đi đỉnh cuối thì trở thành đường. Một hành trình 14 khép kín được gọi là mạch nếu mọi cạnh của nó đều khác nhau. 1.1.3 Tính liên thông Nhiều bài toán có thể được mô hình với các đường đi dọc theo các cạnh của đồ thị. Nhưng cũng có mô hình mà tồn tại hai đỉnh không có đường nối chúng. Do vậy, chúng ta sẽ xét tới tính liên thông của đồ thị. Định nghĩa 1.1.8. Một đồ thị G = (V, E) được gọi là liên thông nếu với hai đỉnh vi và vj khác nhau bất kỳ của G luôn luôn tồn tại một đường đi nối hai đỉnh ấy. Trong trường hợp ngược lại, đồ thị được gọi là không liên thông. Đồ thị con liên thông G0 = (V 0 , E 0 ) của đồ thị (có hướng, vô hướng) G = (V, E) được gọi là một thành phần liên thông 0 0 00 0 của G. nếu G = G[V ] và với mọi V ⊆ V, mà thực sự chứa V , đồ thị 00 G[V ] là không liên thông . Hình 1.5: Đồ thị G với thành phần liên thông G1 và G2 15 Ví dụ 1.1.9. Đồ thị có hướng G = (V, E) cho trong hình là đồ thị không liên thông. Nó có hai thành phần liên thông là G1 và G2 . Đối với đồ thị có hướng ngoài kiểu liên thông định nghĩa ở trên người ta còn định nghĩa kiểu liên thông một chiều kiểu liên thông mạch như sau. Đồ thị có hướng G = (V, E) được gọi là liên thông một chiều, nếu với hai đỉnh khác nhau bất kỳ vi và vj , tồn tại một hành trình có hướng với đỉnh đầu là vi và đỉnh cuối là vj hoặc một hành trình có hướng với đỉnh đầu là vj và đỉnh cuối là vi (hoặc cả hai hành trình đó). Đồ thị có hướng G = (V, E) được gọi là liên thông mạch, nếu với hai đỉnh bất kỳ khác nhau vi và vj , luôn tồn tại cả hành trình có hướng với đỉnh đầu là vi và đỉnh cuối là vj , và hành trình có hướng với đỉnh đầu là vj và đỉnh cuối là vi . 1.1.4 Cây Một đồ thị vô hướng liên thông không có khuyên và không có chu trình được gọi là cây. Một đồ thị vô hướng không có khuyên (không nhất thiết phải là liên thông) và không có chu trình được gọi là rừng. Từ các định nghĩa trên dễ thấy rằng mỗi thành phần liên thông của rừng là cây. Ví dụ 1.1.10. Đồ thị G = (V, E) hình dưới là rừng gồm 4 cây là G1 G2 G3 G4 . 16 Hình 1.6: Ví dụ một rừng gồm 4 cây. Các đỉnh bậc 1 của cây được gọi là đỉnh lá hay đỉnh cuối, còn các đỉnh bậc lớn hơn 1 của cây được gọi là cành hay đỉnh trong. Cấu trúc cây được mô tả bởi định lý sau đây . Định lý 1.1.11. (Định lý móc xích kiểu hoa cúc). Giả sử T = (V, E) là đồ thị vô hướng không có khuyên. Khi đó các khẳng định sau đây là tương đương nhau: (a) T là cây; (b) T không chứa chu trình và |E| = |V | − 1; (c) T liên thông và |E| = |V | − 1; (d) T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì đồ thị nhận được là không liên thông; (e) Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một đường; 17 (f) T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai đỉnh không kề nhau trong T thì đồ thị nhận được có đúng một chu trình. 1.2 1.2.1 Một vài đồ thị đặc biệt Đồ Thị Euler Một vết trong đồ thị vô hướng G = (V, E) được gọi là vết Euler nếu nó chứa tất cả các cạnh của G. Đồ thị vô hướng G = (V, E) được gọi là đồ thị nửa Euler nếu nó có một vết Euler. Hình 1.7: Ví dụ đồ thị không nửa Euler, nửa Euler và Euler. Một mạch trong đồ thị vô hướng G = (V, E) được gọi là mạch Euler nếu nó chứa tất cả các cạnh của đồ thị G. Đồ thị vô hướng G = (V, E) được gọi là đồ thị Euler nếu nó có một mạch Euler. Nếu một đồ thị vô hướng là đồ thị Euler thì hiển nhiên nó cũng là đồ thị nửa Euler. 18 Ví dụ 1.2.1. Trên hình đồ thị G1 không là đồ thị nửa Euler, đồ thị G2 là đồ thị nửa Euler nhưng không là Euler, còn đồ thị G3 là đồ thị Euler. Dưới đây ta sẽ gọi đồ thị vô hướng G là không tầm thường nếu G 6= 01 . Định lý 1.2.2. (Euler, 1736). (a) Một đồ thị vô hướng liên thông không tầm thường G = (V, E) là đồ thị Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn. (b) Một đồ thị vô hướng liên thông không tầm thường G = (V, E) là đồ thị nửa Euler khi và chỉ khi nó không quá hai đỉnh bậc lẻ. Chứng minh. (a) Hiển nhiên rằng nếu đồ thị vô hướng liên thông không tầm thường G = (V, E) là đồ thị Euler thì mọi đỉnh của G đều có bậc chẵn. Thật vậy, chẳng hạn nếu x1 x2 ...xn x1 là mạch Euler trong G và đỉnh x xuất hiện k lần trong mạch đó, thì số cạnh trong G liên thuộc với x là 2k . vì vậy, deg(x) = 2k + 2 nếu {x, x} ∈ E . Trong cả hai trường hợp deg(x) chẵn. Ngược lại, giả sử mọi đỉnh của G = (V, E) đều có bậc chẵn. Ta chứng minh rằng G là đồ thị Euler bằng qui nạp theo |E|. Dễ kiểm tra thấy rằng nếu G là đồ thị thỏa mãn các điều kiện đã nêu với số cạnh |E| ít nhất, thì |E| = 3 và G là chu trình độ dài 3. Khi đó G hiển nhiên cũng là đồ thị Euler. Bây giờ giả sử G = (V, E) là một đồ thị vô hướng liên thông không tầm thường bất kỳ, trong đó mọi đỉnh đều có bậc chẵn . Ta cũng giả thiết rằng mọi đồ thị vô hướng liên thông không tầm thường 0 0 0 0 G = (V , E trong đó mọi đỉnh đều có bậc chẵn và |E| < |E| đều đã