離散數(shù)學課件第八章(第4講)

8.5特殊的圖歐拉圖漢密爾頓圖平面圖對偶圖8.5特殊的圖歐拉圖

歐拉圖

哥尼斯堡七橋問題：

18世紀在哥尼斯堡城(今俄羅斯加里寧格勒)的普萊格爾河上有7座橋，將河中的兩個島和河岸連結(jié)，如下圖所示。城中的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。歐拉圖 哥尼斯堡七橋問題：于是“七橋問題”就等價于上圖能否一筆畫成的問題。歐拉提出不存在一次走遍7座橋，而每座橋只許通過一次的走法。陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地看成4個結(jié)點，7座橋表示成7條連接這4個結(jié)點的邊，如下圖所示。于是“七橋問題”就等價于上圖能否一筆畫成的問題。陸地是橋梁

定義1：給定無孤立結(jié)點圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路。

定義2：給定無孤立結(jié)點圖G，若存在一條回路，經(jīng)過圖中每邊一次且僅一次，該回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。v2v3v4v1（V1、V2、V3、V1、V4、V3）是一條歐拉路定義1：給定無孤立結(jié)點圖G，若存在一條路，經(jīng)過定理1：給定無向連通圖G，G是歐拉圖，當且僅當圖中每個結(jié)點都是偶數(shù)度結(jié)點。定理2：無向圖連通圖G有一條歐拉路，當且僅當G有零個或兩個奇數(shù)度結(jié)點。v2v3v4v1定理1：給定無向連通圖G，G是歐拉圖，當且僅當圖中每個結(jié)點都

例：證明：n階完全無向圖Kn是歐拉圖當且僅當n為奇數(shù)。

證：

n階完全無向圖Kn是連通圖且每個節(jié)點的度數(shù)均為n-1，于是Kn是歐拉圖當且僅當n-1是偶數(shù)，即n為奇數(shù)。例：證明：n階完全無向圖Kn是歐拉圖當且僅當n為奇數(shù)例：從圖中找一條歐拉路。解：有兩個奇數(shù)度結(jié)點:v1和v4，所以存在歐拉路。L=v1,v2,v3,v4,v5,v2,v4

是一條歐拉路。例：從圖中找一條歐拉路。定理3：有向圖G為歐拉圖，當且僅當G是連通的，且每個結(jié)點入度等于出度。定理4：一個有向圖G中具有歐拉路，當且僅當它是連通的，而且除兩個結(jié)點外，每個結(jié)點的入度等于出度，但這兩個結(jié)點中，一個結(jié)點的入度比出度小1，一個結(jié)點的入度比出度大1。定理3：有向圖G為歐拉圖，當且僅當G是連通的，且每個結(jié)點入度歐拉回路問題既是一個有趣的游戲問題,又是一個有實用價值的問題。郵遞員一般的郵遞路線是需要遍歷某些特定的街道,理想地,他應該走一條歐拉路,即不重復地走遍圖中的每一條邊。有的郵遞任務是聯(lián)系某些特定的收發(fā)點,不要求走遍每一條邊,只要求不重復地遍歷圖中的每一個頂點,此時感興趣的是圖中的頂點,這就是下面研究的漢密爾頓圖。歐拉回路問題既是一個有趣的游戲問題,又是一個有實用價值的問漢密爾頓圖1859年,愛爾蘭數(shù)學家漢密爾頓(Halmiton)提出一個“周游世界”的游戲,它把圖(a)所示的正十二面體的二十個頂點當作是地球上的二十個城市,要求旅游者從某個城市出發(fā),沿棱走過每個城市一次且僅一次,最后回到出發(fā)點。(b)圖中粗線所構(gòu)成的回路就是問題的答案。ab漢密爾頓圖1859年,愛爾蘭數(shù)學家漢密爾頓(Ha

定義1：給定圖G，若存在一條通路，經(jīng)過圖中的每個結(jié)點恰好一次，這條通路稱作漢密爾頓路。

定義2：給定圖G，若存在一條回路，經(jīng)過圖中的每個結(jié)點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。定義1：給定圖G，若存在一條通路，經(jīng)過圖中的每個結(jié)點例：(a)存在漢密爾頓回路,(a)是漢密爾頓圖。(b)存在漢密爾頓通路但不存在漢密爾頓回路,(b)不是漢密爾頓圖。(c)不存在漢密爾頓通路且不存在漢密爾頓回路,(c)不是漢密爾頓圖。（a）（b）（c）例：(a)存在漢密爾頓回路,(a)是漢密爾頓圖。（a）（b練習：一只小螞蟻可否從立方體的一個頂點出發(fā)，沿著棱爬行，它爬過每一個頂點一次且僅一次，最后回到原出發(fā)點？練習：一只小螞蟻可否從立方體的一個頂點出發(fā)，沿著棱爬行，例：證明：若一個無向圖G=(V，E)存在一個節(jié)點v,使得deg(v)=1，則G不是漢密爾頓圖。證:

因為圖G的漢密爾頓回路要經(jīng)過節(jié)點v，這是顯然deg(v)≥2，故G不是漢密爾頓圖。例：證明：若一個無向圖G=(V，E)存在一個節(jié)點v,使得定理1：若圖G=<V，E>為漢密爾頓圖，則對于結(jié)點集V的每個非空子集S(真子集S

)有：W(G-S)≤|S|成立，其中W(G-S)是G-S中的連通分支數(shù)。(必要條件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6定理1：若圖G=<V，E>為漢密爾頓圖，則對于結(jié)

定理2：設圖G是有n個結(jié)點的簡單無向圖，若G中任意兩個結(jié)點度數(shù)之和大于等于n，則G是漢密爾頓圖。（這是充分條件，但不是必要條件）（a）（b）定理2：設圖G是有n個結(jié)點的簡單無向圖，若G中任歐拉圖和漢密爾頓圖之間的區(qū)別：(1)歐拉回路是簡單回路,而漢密爾頓圖回路是基本回路。簡單回路：各邊都不相同的回路?；净芈罚撼K點與始點外，其它結(jié)點都不相同的回路。(2)歐拉圖遍歷邊,而漢密爾頓圖遍歷頂點。歐拉圖和漢密爾頓圖之間的區(qū)別：(1)歐拉回路是簡單回路,而

平面圖例：K3,3圖如下，試問：能否轉(zhuǎn)變成與其等價的，且使得任何兩條邊除了端點外沒有其它的交點的平面上的圖？

456定義1：設G=<V,E>是一個無向圖，如果能夠把G的所有結(jié)點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其它的交點，就稱G是一個平面圖。平面圖例：K3,3圖如下，試問：能否轉(zhuǎn)變成與其等判斷一個圖是否為平面圖的簡單方法是觀察法：找出基本循環(huán)，將交叉的邊分別放置在基本循環(huán)內(nèi)或外而避免交叉。如下圖所示：但并非所有的圖經(jīng)過處理之后都可變?yōu)槠矫鎴D。判斷一個圖是否為平面圖的簡單方法是觀察法：但并非所有的

定義2：設G是一連通平面圖，由圖中的邊所包圍的區(qū)域，且在該區(qū)域內(nèi)既不包含圖的結(jié)點，也不包含圖的邊，這樣的區(qū)域稱為G的面。包圍一個面的諸邊稱為此面的邊界。面的面積為有限者稱為有限面，面的面積為無限者稱為無限面。

例：Ⅰ為有限面Ⅱ為無限面定義2：設G是一連通平面圖，由圖中的邊所包圍的區(qū)域，定義3：一個面的邊界的回路長度稱作是該面的次數(shù)，記為：deg(r)定理1：一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。證明：對于G中的每一條邊e，e或是兩個面的公共邊，或是在一個面中為懸掛邊被作為邊界計算兩次，故定理成立。定義3：一個面的邊界的回路長度稱作是該面的次數(shù)，記為：deg

定理2：(歐拉定理)設圖G是一個n個結(jié)點,m條邊的連通平面圖，它的面數(shù)為r，則有歐拉公式：

n－m＋r＝2。證明:用歸納法

m=0時，G為平凡圖，n=1，r=1，公式成立。定理2：(歐拉定理)設圖G是一個n個結(jié)點,m條邊的連

設m=k-1（k≥1）時公式成立，現(xiàn)在考慮m=k時的情況。因為在連通圖上增加一條邊仍為連通圖，則有三種情況：（1）所增邊為懸掛邊，此時G的面數(shù)不變，頂點數(shù)增1，公式成立。（2）在圖的任意兩個不相鄰點間增加一條邊，此時G的面數(shù)增1，邊數(shù)增1，但頂點數(shù)不變，公式成立。（3）所增邊為一個環(huán)，此時G的面數(shù)增1，邊數(shù)增1，但頂點數(shù)不變，公式成立。設m=k-1（k≥1）時公式成立，現(xiàn)在考慮m=k時的

練習：在由6個結(jié)點，12條邊構(gòu)成的連通簡單平面圖中，每個面由幾條邊圍成？練習：

定理3:設G是一個包含n個結(jié)點,m條邊的連通簡單平面圖，且每個面的次數(shù)至少為l（l≥3），則定理3:設G是一個包含n個結(jié)點,m條邊的連通簡單平面于是有故

證明:由定理1(r為G的面數(shù))再由歐拉公式n-m+r=2于是有故證明:由定理1(r為G的面數(shù))再由歐拉公式

推論1:設圖G是一個包含n個結(jié)點,m條邊的連通簡單平面圖，若n≥3,則m≤3n-6。

證明：由于G是n≥3的簡單連通平面圖，所以G的每個面至少由3條邊圍成，即l≥3，由定理3得m≤3n-6.

推論1:設圖G是一個包含n個結(jié)點,m條邊的連通簡單平面圖推論1給出了平面圖的必要條件，若不滿足這些條件，則一定不是平面圖。例：K5圖不是平面圖。推論1給出了平面圖的必要條件，若不滿足這些條件，則一定例：證明當每個結(jié)點的度數(shù)大于等于3時，不存在7條邊的連通簡單平面圖。證：

(反證)：設G是(n，m)圖，若m=7，根據(jù)推論1知，m≤3n-6，即7≤3n-6，于是3n≥13。根據(jù)握手定理，有即3n≤14。這與3n≥13矛盾。例：證明當每個結(jié)點的度數(shù)大于等于3時，不存在7條邊的連練習：

(1)設G是包含n個結(jié)點(n≥3),m條邊的連通簡單平面圖，證明G中至少有一個結(jié)點的度數(shù)小于等于5。(2)設G是包含n個結(jié)點(n≥3),邊數(shù)m小于30的連通簡單平面圖，證明G中存在結(jié)點v,d(v)≤4。練習：

推論2:若連通簡單平面圖G不以K3為子圖，則m≤2n-4。證明:由于G中不含K3，所以G的每個面至少由4條邊圍成，即l≥4，代入定理3，得m≤2n-4.推論2:若連通簡單平面圖G不以K3為子圖，則例：證明K5和K3，3是非平面圖。證明:假設K5是平面圖，由推論1可知應有m≤3n-6，而當n=5，m=10時，這是不可能的，所以K5是非平面圖。假設K3，3是平面圖，因其不含子圖K3，由推論2可知，當n=6，m=9時，m≤2n-4是不可能的，所以K3，3是非平面圖。例：證明K5和K3，3是非平面圖。(2)若e是G中兩個不同面Ri和Rj的公共邊，則存在且僅存在一條邊e*k∈G*與e相交；(3)若e是一個面Ri內(nèi)的邊，則在G*中有一條與e交叉的環(huán)。則稱G*為G的對偶圖，G*與G互為對偶圖。定義

設平面圖G=〈V,E〉有r個面R1，R2，…，Rr，若有圖G*=〈V*,E*〉滿足下述條件：(1)Ri∈G，內(nèi)部有且僅有一個結(jié)點v*i∈V*，i=1，2，…，r。1.對偶圖

對偶圖(2)若e是G中兩個不同面Ri和Rj的公共邊，則存在例:圖（a）和（b）中，G*是G的對偶圖，G的邊用實線表示，G*的邊用虛線表示。（a）（b）例:圖（a）和（b）中，G*是G的對偶圖，G的邊用實線表示，2.著色問題在地圖上，相鄰國家涂不同的顏色，最少需要多少種顏色？100多年前，有人提出了“四色猜想”，即只用四種顏色就能做到，但一直無法證明，直到1976年美國數(shù)學家才用電子計算機證明了這一猜想。地圖著色自然是對平面圖的面著色，利用對偶圖，可將其轉(zhuǎn)化為相對簡單的頂點著色問題，即對圖中相鄰的頂點涂不同的顏色。2.著色問題韋爾奇·鮑威爾（WelchPowell）給出了一種對圖的著色方法，步驟如下：（1）將圖G中的頂點按度數(shù)遞減次序排列。（2）用第一種顏色對第一頂點著色，并將與已著色頂點不鄰接的頂點也著第一種顏色。（3）按排列次序用第二種顏色對未著色的頂點重復（2）。用第三種顏色繼續(xù)以上做法，直到所有的頂點均著上色為止。韋爾奇·鮑威爾（WelchPowell）給出了一種對圖的著色例:用韋爾奇·鮑威爾法對下圖著色。（1）各頂點按度數(shù)遞減次序排列：c，a，e，f，b，h，g，d。（2）對c和與c不鄰接的e，b著第一種顏色。（3）對a和與a不鄰接的g，d著第二種顏色。（4）對f和與f不鄰接的h著第三種顏色。例:用韋爾奇·鮑威爾法對下圖著色。8.5特殊的圖歐拉圖漢密爾頓圖平面圖對偶圖8.5特殊的圖歐拉圖

歐拉圖

哥尼斯堡七橋問題：

18世紀在哥尼斯堡城(今俄羅斯加里寧格勒)的普萊格爾河上有7座橋，將河中的兩個島和河岸連結(jié)，如下圖所示。城中的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。歐拉圖 哥尼斯堡七橋問題：于是“七橋問題”就等價于上圖能否一筆畫成的問題。歐拉提出不存在一次走遍7座橋，而每座橋只許通過一次的走法。陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地看成4個結(jié)點，7座橋表示成7條連接這4個結(jié)點的邊，如下圖所示。于是“七橋問題”就等價于上圖能否一筆畫成的問題。陸地是橋梁

定義1：給定無孤立結(jié)點圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路。

定義2：給定無孤立結(jié)點圖G，若存在一條回路，經(jīng)過圖中每邊一次且僅一次，該回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。v2v3v4v1（V1、V2、V3、V1、V4、V3）是一條歐拉路定義1：給定無孤立結(jié)點圖G，若存在一條路，經(jīng)過定理1：給定無向連通圖G，G是歐拉圖，當且僅當圖中每個結(jié)點都是偶數(shù)度結(jié)點。定理2：無向圖連通圖G有一條歐拉路，當且僅當G有零個或兩個奇數(shù)度結(jié)點。v2v3v4v1定理1：給定無向連通圖G，G是歐拉圖，當且僅當圖中每個結(jié)點都

例：證明：n階完全無向圖Kn是歐拉圖當且僅當n為奇數(shù)。

證：

n階完全無向圖Kn是連通圖且每個節(jié)點的度數(shù)均為n-1，于是Kn是歐拉圖當且僅當n-1是偶數(shù)，即n為奇數(shù)。例：證明：n階完全無向圖Kn是歐拉圖當且僅當n為奇數(shù)例：從圖中找一條歐拉路。解：有兩個奇數(shù)度結(jié)點:v1和v4，所以存在歐拉路。L=v1,v2,v3,v4,v5,v2,v4

是一條歐拉路。例：從圖中找一條歐拉路。定理3：有向圖G為歐拉圖，當且僅當G是連通的，且每個結(jié)點入度等于出度。定理4：一個有向圖G中具有歐拉路，當且僅當它是連通的，而且除兩個結(jié)點外，每個結(jié)點的入度等于出度，但這兩個結(jié)點中，一個結(jié)點的入度比出度小1，一個結(jié)點的入度比出度大1。定理3：有向圖G為歐拉圖，當且僅當G是連通的，且每個結(jié)點入度歐拉回路問題既是一個有趣的游戲問題,又是一個有實用價值的問題。郵遞員一般的郵遞路線是需要遍歷某些特定的街道,理想地,他應該走一條歐拉路,即不重復地走遍圖中的每一條邊。有的郵遞任務是聯(lián)系某些特定的收發(fā)點,不要求走遍每一條邊,只要求不重復地遍歷圖中的每一個頂點,此時感興趣的是圖中的頂點,這就是下面研究的漢密爾頓圖。歐拉回路問題既是一個有趣的游戲問題,又是一個有實用價值的問漢密爾頓圖1859年,愛爾蘭數(shù)學家漢密爾頓(Halmiton)提出一個“周游世界”的游戲,它把圖(a)所示的正十二面體的二十個頂點當作是地球上的二十個城市,要求旅游者從某個城市出發(fā),沿棱走過每個城市一次且僅一次,最后回到出發(fā)點。(b)圖中粗線所構(gòu)成的回路就是問題的答案。ab漢密爾頓圖1859年,愛爾蘭數(shù)學家漢密爾頓(Ha

定義1：給定圖G，若存在一條通路，經(jīng)過圖中的每個結(jié)點恰好一次，這條通路稱作漢密爾頓路。

定義2：給定圖G，若存在一條回路，經(jīng)過圖中的每個結(jié)點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。定義1：給定圖G，若存在一條通路，經(jīng)過圖中的每個結(jié)點例：(a)存在漢密爾頓回路,(a)是漢密爾頓圖。(b)存在漢密爾頓通路但不存在漢密爾頓回路,(b)不是漢密爾頓圖。(c)不存在漢密爾頓通路且不存在漢密爾頓回路,(c)不是漢密爾頓圖。（a）（b）（c）例：(a)存在漢密爾頓回路,(a)是漢密爾頓圖。（a）（b練習：一只小螞蟻可否從立方體的一個頂點出發(fā)，沿著棱爬行，它爬過每一個頂點一次且僅一次，最后回到原出發(fā)點？練習：一只小螞蟻可否從立方體的一個頂點出發(fā)，沿著棱爬行，例：證明：若一個無向圖G=(V，E)存在一個節(jié)點v,使得deg(v)=1，則G不是漢密爾頓圖。證:

因為圖G的漢密爾頓回路要經(jīng)過節(jié)點v，這是顯然deg(v)≥2，故G不是漢密爾頓圖。例：證明：若一個無向圖G=(V，E)存在一個節(jié)點v,使得定理1：若圖G=<V，E>為漢密爾頓圖，則對于結(jié)點集V的每個非空子集S(真子集S

)有：W(G-S)≤|S|成立，其中W(G-S)是G-S中的連通分支數(shù)。(必要條件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6定理1：若圖G=<V，E>為漢密爾頓圖，則對于結(jié)

定理2：設圖G是有n個結(jié)點的簡單無向圖，若G中任意兩個結(jié)點度數(shù)之和大于等于n，則G是漢密爾頓圖。（這是充分條件，但不是必要條件）（a）（b）定理2：設圖G是有n個結(jié)點的簡單無向圖，若G中任歐拉圖和漢密爾頓圖之間的區(qū)別：(1)歐拉回路是簡單回路,而漢密爾頓圖回路是基本回路。簡單回路：各邊都不相同的回路?；净芈罚撼K點與始點外，其它結(jié)點都不相同的回路。(2)歐拉圖遍歷邊,而漢密爾頓圖遍歷頂點。歐拉圖和漢密爾頓圖之間的區(qū)別：(1)歐拉回路是簡單回路,而

平面圖例：K3,3圖如下，試問：能否轉(zhuǎn)變成與其等價的，且使得任何兩條邊除了端點外沒有其它的交點的平面上的圖？

456定義1：設G=<V,E>是一個無向圖，如果能夠把G的所有結(jié)點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其它的交點，就稱G是一個平面圖。平面圖例：K3,3圖如下，試問：能否轉(zhuǎn)變成與其等判斷一個圖是否為平面圖的簡單方法是觀察法：找出基本循環(huán)，將交叉的邊分別放置在基本循環(huán)內(nèi)或外而避免交叉。如下圖所示：但并非所有的圖經(jīng)過處理之后都可變?yōu)槠矫鎴D。判斷一個圖是否為平面圖的簡單方法是觀察法：但并非所有的

定義2：設G是一連通平面圖，由圖中的邊所包圍的區(qū)域，且在該區(qū)域內(nèi)既不包含圖的結(jié)點，也不包含圖的邊，這樣的區(qū)域稱為G的面。包圍一個面的諸邊稱為此面的邊界。面的面積為有限者稱為有限面，面的面積為無限者稱為無限面。

例：Ⅰ為有限面Ⅱ為無限面定義2：設G是一連通平面圖，由圖中的邊所包圍的區(qū)域，定義3：一個面的邊界的回路長度稱作是該面的次數(shù)，記為：deg(r)定理1：一個有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。證明：對于G中的每一條邊e，e或是兩個面的公共邊，或是在一個面中為懸掛邊被作為邊界計算兩次，故定理成立。定義3：一個面的邊界的回路長度稱作是該面的次數(shù)，記為：deg

定理2：(歐拉定理)設圖G是一個n個結(jié)點,m條邊的連通平面圖，它的面數(shù)為r，則有歐拉公式：

n－m＋r＝2。證明:用歸納法

m=0時，G為平凡圖，n=1，r=1，公式成立。定理2：(歐拉定理)設圖G是一個n個結(jié)點,m條邊的連

設m=k-1（k≥1）時公式成立，現(xiàn)在考慮m=k時的情況。因為在連通圖上增加一條邊仍為連通圖，則有三種情況：（1）所增邊為懸掛邊，此時G的面數(shù)不變，頂點數(shù)增1，公式成立。（2）在圖的任意兩個不相鄰點間增加一條邊，此時G的面數(shù)增1，邊數(shù)增1，但頂點數(shù)不變，公式成立。（3）所增邊為一個環(huán)，此時G的面數(shù)增1，邊數(shù)增1，但頂點數(shù)不變，公式成立。設m=k-1（k≥1）時公式成立，現(xiàn)在考慮m=k時的

練習：在由6個結(jié)點，12條邊構(gòu)成的連通簡單平面圖中，每個面由幾條邊圍成？練習：

定理3:設G是一個包含n個結(jié)點,m條邊的連通簡單平面圖，且每個面的次數(shù)至少為l（l≥3），則定理3:設G是一個包含n個結(jié)點,m條邊的連通簡單平面于是有故

證明:由定理1(r為G的面數(shù))再由歐拉公式n-m+r=2于是有故證明:由定理1(r為G的面數(shù))再由歐拉公式

推論1:設圖G是一個包含n個結(jié)點,m條邊的連通簡單平面圖，若n≥3,則m≤3n-6。

證明：由于G是n≥3的簡單連通平面圖，所以G的每個面至少由3條邊圍成，即l≥3，由定理3得m≤3n-6.

推論1:設圖G是一個包含n個結(jié)點,m條邊的連通簡單平面圖推論1給出了平面圖的必要條件，若不滿足這些條件，則一定不是平面圖。例：K5圖不是平面圖。推論1給出了平面圖的必要條件，若不滿足這些條件，則一定例：證明當每個結(jié)點的度數(shù)大于等于3時，不存在7條邊的連通簡單平面圖。證：

(反證)：設G是(n，m)圖，若m=7，根據(jù)推論1知，m≤3n-6，即7≤3n-6，于是3n≥13。根據(jù)握手定理，有即3n≤14。這與3n≥13矛盾。例：證明當每個結(jié)點的度數(shù)大于等于3時，不存在7條邊的連練習：

(1)設G是包含n個結(jié)點(n≥3),m條邊的連通簡單平面圖，證明G中至少有一個結(jié)點的度數(shù)小于等于5。(2)設G是包含n個結(jié)點(n≥3),邊數(shù)m小于30的連通簡單平面圖，證明G中存在結(jié)點v,d(v)≤4。練習：

推論2:若連通簡單平面圖G不以K3為子圖，則m≤2n-4。證明:由于G中不含K3，所以G的每個面至少由4條邊圍成，即l≥4，代入定理3，得m≤2n-4.推論2:若連通簡單平面圖G不以K3為子圖，則例：證明K5和K3，3是非平面圖。證明: