1、d(v) 2mv V(G)定理1 : 圖G= (V, E)中所有頂點的度的和等于邊數m的2倍,即：推論1在任何圖中,奇點個數為偶數.推論2正那么圖的階數和度數不同時為奇數.定理2假設n階簡單圖G不包含Kl+1 ,那么G度弱于某個完全l部G H圖H,且假設G具有與H相同的度序列,那么：定理3設T是(n, m)樹,那么：m n 1偶圖判定定理：定理4圖G是偶圖當且僅當G中沒有奇回路.敏格爾定理：定理5 (1) 設x與y是圖G中的兩個不相鄰點,那么G中別離點x與y的最小點數等于獨立的(x, y)路的最大數目；(2)設x與y是圖G中的兩個不相鄰點,那么 G中別離點x與y的最小邊數等于G中邊不重的(x,

2、 y)路的最大數目.歐拉圖、歐拉跡的判定：定理6以下陳述對于非平凡連通圖G是等價的：(1) G是歐拉圖；(2) G的頂點度數為偶數； (3) G的邊集合能劃分為圈.推論：連通非歐拉圖G存在歐拉跡當且僅當 G中只有兩個頂點度數為奇數.那么G是H圖；并且,具有n個頂點 n 11條邊的非H圖2只有C1,n以及C2,5.定理13 (Hall定理)設對Gg 女名惘5)那么鹵,件和X每個頂 點的匹配的充要條件是：推論：假設G是k (k>0)正那么偶圖,那么G存在完美匹配.定理 14 (哥尼,1931)在偶圖中,最大匹配的邊數等于最小覆蓋的頂點數.定理15 K2n可一因子分解. 定理16 具有H圈的三

3、正那么圖可一因子分解.定理17 K2n+1可2因子分解.定理18 K2n可分解為一個1因子和n-1個2因子之和.定理19 每個沒有割邊的3正那么圖是一個1因子和1個2因子之和.假設n為偶數,且S (G) >n/2+1,那么n階圖G有3因子定理20設G=(n, m)是平面圖,那么：,deg(f)2m,n m 2定理21(歐拉公式)設G=(n, m)是連通平面圖,力是 G的面數,那么:推論1設G是具有n個點m條邊力個面的率通平面圖,如果對 G m l 2(n 2)的每個面f ,有：deg (f)> l >3,那么：定理29設G是奇數階正那么單圖,假設.,那么：(G)(G) 1定理

4、31(布魯克斯,1941)假設G是連通的單圖,并且它既不是奇圈,又不是完全圖,那么：(G)(G)(m 1)i t定理32在完全m元樹T中,假設樹葉數為t ,分支點數為i ,那么：)根樹：一棵非平凡的有向樹 T,如果恰有一個頂點的入度為0,而其余所有頂點的入度為1,這樣的的有向樹稱為根樹.其中入度為0的點稱為樹根,出度為 0的點稱為樹葉,入度為1,出度大于1的點稱為內點.又將內點和樹根統稱為分支點.敏格爾定理：定理5 (1) 設x與y是圖G中的兩個不相鄰點,那么G中別離點x與y的最小點數等于獨立的(x, y)路的最大數目；2)設x與y是圖G中的兩個不相鄰點,那么 G中別離點x與y的最小邊數等于G

5、中邊不重的(x, y)路的最大數目.例2 (排課表問題)在一個學校中,有7個教師12個班級.在 每周5天教學日條件下,教課的要求由如下矩陣給出:32 3 33 3 3333 3 313604251330450 5 50 0 505 0 55P 24242424242335 2 20 3 144 3 2555 0 05 5 050 5 50H圖的判定：定理7 (必要條件)假設G為H圖,那么對V(G)的任一非 (G S) S空頂點子集S,有：0、 n(G)2定理8 (充分條件)對于n3的單圖G,如果G中有：定理9 (充分條件)對于n3的單圖G如果G中的任意兩個不d (u) d (v) n相鄰頂點u

6、與v,有：定理10 (幫迪一一1包定理)圖G是H圖當且僅當它的閉包是 H圖.推論2設G是具有n個點m條邊力個面的簡單平面圖,推論3設G是具有n個點m條邊的簡單平面圖,那么：定理22平面圖G的對偶圖必然連通定理11(Chv dal一一度序列判定法)設簡單圖 G的度序列是(d1,d2,dn),這里,d1三d2三三dn,并且n3.假設對任意的m<n/2,或者 dm>m,或者 dn-m叁n-m,那么蜒山圖I 1定理12設G是n階單圖.假設n3且那么.m 3n 6問題可模型為一個偶圖.5一節課對應邊正常著色的一個色組.由于G是偶圖,所以邊色數為G的最大度35o這樣,最少總課時為35節課.平均

7、每天要安排定理23設G是至少有3個頂點的平面圖,那么G是極大平面圖,當 .、中7節課且,K G)勺每個面的次數是3且為單圖.定理25 (哥尼,1916)假設G是偶圖,那么 (G)定理26 (維津定理,1964)假設G是單圖,那么：(G) 或(G)+1定理27設G是單圖且4 (G)>0.假設G中只有一個最大度點或恰有兩個相鄰的最大度點,那么:定理28設G是單圖.假設點數如果每天安排8節課,由于G的總邊數為240,所以需要的教室數為240/40=6(G)(G)n=2k+1且邊數 m>kA ,那么:定理5 一個n階圖G相和它的補圖有相同的頻序列.邊不重復的途徑稱為跡；點不重復的途徑稱為路

8、.顯然路 必為跡.圖 G的直徑定義為 d(G) = max d(u, v) | u, v V(G)(G)/明假設6?2,那么G中必然含有圈.證實：只就連通圖證實即可！設 W=v1v2.vk-1vk 是G中的一條最長路.由于S>2,03 4 34 3 434 3 30根本回路是點不重復,簡單回來,邊不重所以vk必然有相異于vk-1的鄰接頂點.又W是G中最長路.所以,這樣的鄰接點必然是v1,v2,.,vk-2中之一.設該點為 vm 那么 vmvm+1- .v kvm 為 G中圈.設G是具有m條邊的n階單圖,證實：假設 G的直徑為2且4 (G)=n-2,那么m > 2n-4.證實：設d

9、(v)= A=n-2,且設v的鄰接點 為v1,v2,vn-2. u 是剩下的一個頂點.由于 d (G)=2且u不能 和v鄰接,所以u必須和v1,v2,vn-2中每個頂點鄰接.否那么有d (G)>2.于是得：m > 2n-4.定理8 一個圖是偶圖當且當它不包含奇圈.證實 設G是具有二分類(X, Y)的偶圖,并且 C = v0 v1vk v0是G的一個圈.不失一般性,可假定v0 G X.這樣,v2i X ,且v2i +1 Y o又由于v0 G X ,所以vk G Y.由此即得 C是偶圈.顯然僅對連通圖證實其逆命題就夠了. 設G是不包含奇 圈的連通圖.任選一個頂點 u且定義V的一個分類(

10、X, Y)如下：X = x | d (u, x)是偶數,xGV(G)Y = y | d (u, y)是奇數,yG V(G)現在證實(X, Y)是G的一個二分類.假設v和w是X的兩個頂點,P是最短的(u,v)路,Q是最短的(u, w)路,以u1記P和Q的最后一個公共頂 點.因P和Q是最短路,P和Q二者的(u1, u)節也是最短的路, 故長相同.現因P和Q的長都是偶數,所以 P的(u1, v )節P1 和Q的(u1,w)節Q1必有相同的奇偶性.由此推出路( v, w ) 長為偶數.假設v和w相連,那么就是一個奇圈,與假設矛盾,故X中任意兩個頂點均不相鄰.設A為4圈C4的鄰接矩陣,求A的譜.所以今白

11、沙儀值為-2 , 0, 2 ;其重數依次記為1,2,1.故Spec A =12 11設G是具有n個點m條邊的圖,那么以下關于樹的命題等價. (1) G是樹.(2) G中任意兩個不同點之間存在唯一的路.(3) G連通,刪去任一邊便不連通(4) G連通,且m = n-1.5) G無圈,且m = n-1. (6) G無圈,添加任一條邊可得唯一的圈ET口一兇XX一 01L由M(G)(Ge)(G定義2 設T是圖G= (V, E)的一棵生成樹,m和n分別是G的 邊數與頂點數,e1, e2,em-n+1為T的弦,設Cr是T加er 產生的圈,r = 1,2 ,m-n+1,稱Cr為對應于弦er的根本回路,稱C1

12、,C2,Cm-n+1為對應于生成樹 T的根本回路系統.粗l世下闌巾,力一比價困.向新舶TtlriWl 依舊,M別JP可向于%,叮門的星布巨蹈.定理8連通圖G的任一回路均可表示成假設干個根本回路的對稱差.(1)假設3 (G-v) >3 (G),那么v必為G的割點；(2)假設G無環且非 平凡,那么 v 是 G 的害U點當且僅當 3 (G-v) >3 (G) 定理3 設v是無環連通圖 G的一個頂點,那么v是G的割點當且僅當V(G-v)可劃分為兩個非空頂點子集V1與V2,使xGV1, yGV2,點v都在每一條(x, y) 路上.假設e是圖G的割邊或e是一個環,那么Ge是G的塊;G的僅含一個

13、點的塊或是孤立點 ,或是環導出的子圖;至少兩個點的塊無環,至少三個點的塊無割邊.定理4設圖G的階至少為3,那么G是塊當且僅當G無環并且任意 兩點都位于同一個圈上.推論 設G的階至少為3,那么G是塊當且僅當G無孤立點且任意兩 條邊都在同一個圈上.定理5點v是圖G的割點當且僅當v至少 屬于G的兩個不同的塊.圖G是2邊連通的當且僅當 G連通、無割邊且至少含有兩個點.引理1 設G是n階簡單圖,假設S (G)> n/2那么G必連通.定理8設G是n階簡單圖,對正整數k<n,假設那么G是k連通的.定理5(Chv dtal 度序列判定法)設簡單圖G的度序列是(d1,d2,dn), 這里,d1三d2

14、三三dn,并且n3.假設對任意的mvn/2,或有dm>m,或有dn-m三n-m,那么G是H圖.證實：假設n為偶數,且S (G) > n/2+1 ,那么n階圖G有3因子.證 明：因S (G)> n/2+1 ,由狄拉克定理：n階圖G有H圈C .又因n 為偶數,所以C為偶圈.于是由C可得到G的兩個1因子.設其 中一個為F1o考慮 G1=G-Ft那么S (G1) >n/2 o于是 G1中有H圈 C1.作+CUFI.顯然H是G的一個3因子證實K5和K 3,3是 不可平面圖.引理 設G是極大平面圖,那么 G必連通；假設G的點數n>3,那么G 無割邊.(1)假設G不連通,那么G至少存在兩個連通分支 G1與G2. 顯然G1與G2也是平面圖.將 G2畫在G1的外部面內,并分別在 G1與G2的外部面上各取一個點u和Vo很明顯,u與v不相鄰.連接u和v,記所得的圖為 G*.易知G*也是平面圖,這與 G是極 大平面圖矛盾,所以 G連通.推論 設G是一個有n個點m條邊力 個面的極大平面圖,n>3,那么 (1) m = 3n-6 ;(2)力=2n-4 o定理12 設G*是平面圖G的對偶圖,那么G*必連通.)同構的平面 圖可以有不同構的對偶圖.對于3階以上的具有m條邊的單圖G 來說,如