圖論問題選講

2009年江蘇省高中數(shù)學(xué)夏令營講義：圖論問題選講馮惠愚2009．07．15．-PAGE5-圖論問題選講由若干個不同的點及連接其中某些點對的線所組成的一種圖形就稱為圖．圖中的點的集合，稱為圖的點集，記為V：V＝{v1，v2，…，vn，…}；圖中的線的集合，稱為圖的線集，記為E：E＝{vivj}(vi，vj∈V)．故一個圖由其點集V和線集E所決定，若用G表示圖，則記為G＝G(V；E)．含有n個點(|v|＝n，記號|M|表示有限集M中元素的個數(shù)，稱為濃度)的圖稱為n階圖．n階圖中共有Ceq\o(\s\up5(2),\s\do3(n))個點對，每對點有鄰接或不鄰接兩種可能情形，故點集為V＝{v1，v2，v3，…，vn}的n階圖共有2eq\s\up5(C\o(\s\up3(2),\s\do2(n)))個．在一個圖中，如果某點V共連了k條線，則說此點的“次數(shù)”(或“度數(shù)”)為k，記為degV＝k．線數(shù)最多的p階圖(即每個點對都連了1條線，共連出了Ceq\o(\s\up5(2),\s\do2(p))條線)稱為p階完全圖，通常記為Kp，如果一個n階圖的每個點的度數(shù)均等于r，則稱之為n階r度正則圖．例1．空間6點，無3點共線，每兩點連1條線，染紅或藍．⑴求證：必存在1個以其中三點為頂點的三角形．三邊同色；⑵求證：必存在2個以其中三點為頂點的三角形．三邊同色．⑶空間5點，無3點共線，每兩點連1條線，染紅或藍，是否一定存在1個以其中三點為頂點的三角形．三邊同色？⑷把數(shù)1，2，3，4，5任意分成兩組，試證明：在這兩組數(shù)中，總有一組數(shù)中存在兩個數(shù)，它們的差(的絕對值)也在這一組中．例2．6人相互認識或相互不認識，只有當(dāng)其中4人圍坐一圈，相鄰2人都互相認識或都互相不認識時，這4人才能坐在一起打牌，問能否找到4人，這4人能夠在一起打牌．例3．給定空間中的9個點，任意4點不共面，每兩點間連一線段．求最小的n值，使當(dāng)對其中任意n條線段用紅、藍兩色之一任意染色時，都一定出現(xiàn)一個三邊同色的三角形．例4．給定平面上的點集P={P1，P2，…，P1994},P中任三點均不共線，將P中的所有的點任意分成83組，使得每組至少有3個點，且每點恰好屬于一組，然后將在同一組的任兩點用一條線段相連，不在同一組的兩點不連線段，這樣得到一個圖案G，不同的分組方式得到不同的圖案，將圖案G中所含的以P中的點為頂點的三角形個數(shù)記為m(G)．(1)求m(G)的最小值m0．(2)設(shè)G*是使m(G*)=m0的一個圖案，若G*中的線段(指以P的點為端點的線段)用4種顏色染色,每條線段恰好染一種顏色．證明存在一個染色方案,使G*染色后不含以P的點為頂點的三邊顏色相同的三角形．鏈：若在一個圖G＝(V；E)中取n＋1個頂點v1、v2、…、vn+1，每兩個相鄰的頂點vi、vi+1間連有一條邊li，則邊l1，l2，…，ln就稱為從v1到vn+1的一條鏈，n稱為鏈的長度．一條鏈的兩個端點v1與vn+1重合時，就稱為圈．如果圖G的任何兩個頂點之間都有一條鏈，就說這個圖是連通的，否則就是不連通的．頂點的次數(shù)為奇數(shù)，則稱此頂點為奇頂點。當(dāng)頂點的次數(shù)為偶數(shù)時，就稱此頂點為偶頂點．任何圖的奇頂點個數(shù)為偶數(shù)．圖G是一筆畫的充分必要條件是G是連通的有限圖，其奇頂點的個數(shù)為0或2．并且當(dāng)且僅當(dāng)奇頂點的個數(shù)為0時，連通圖G是一個圈．沒有圈的連通圖稱為樹．⑴如果樹T的頂點數(shù)為n，則其邊數(shù)為n－1．⑵如果圖G是連通的，且有n個頂點與n－1條邊，則G是一個樹．樹T具有以下性質(zhì)：⑴在T中去掉任一邊后，所得的圖是不連通的；⑵在T中添上1條邊后，所得的圖有圈；⑶T中的任兩個頂點v1與v2間有且僅有1條鏈．例5．在88棋盤的方格中分別填寫1，2，…，82，每格一個數(shù)．證明：必有兩個相鄰方格(有公共邊的方格)，方格中的兩個數(shù)的差至少為5．例6．⑴證明：有n個頂點且不含三角形的圖G的最大邊數(shù)為eq\b\bc\[(\f(n2,4))．⑵設(shè)Z為空間含有n(n≥4)個點的點集，其中任意四點不共面，這些點之間連有eq\b\bc\[(\f(n2,4))＋1條線段．證明：這些線段必可構(gòu)成兩個有公共邊的三角形．(當(dāng)n為偶數(shù)時的情況即是1987年國家集訓(xùn)隊選拔考試題)例7．S為m個無序正整數(shù)對(a，b)(即(a，b)與(b，a)是相同的)(1≤a，b≤n，a≠b)組成的集合．證明：至少有eq\f(4m,3n)(m－eq\f(n2,4))個三元數(shù)組(a，b，c)，適合：(a，b)，(b，c)，(c，a)都屬于S．

例8．十個學(xué)生參加一次考試，試題共有十道，已知沒有兩個學(xué)生做對的題目完全相同，證明：這十道題中可以找到一道題，把這道題取消后，每兩個學(xué)生所做對的題目仍不會全同．(假定每個題，都只有做對與做錯這兩種情況，沒有部分對的情況發(fā)生)例9．n名兒童希望把m塊形狀為矩形的相同的巧克力分成重量相等的n份(n，m∈N*)．規(guī)定每塊巧克力至多被分成兩塊．對怎樣的n與m，上述要求能實現(xiàn)？例10．亞瑟王(傳說中的英國國王)在王宮中召見他的2n名騎士，其中某些騎士之間互相有仇，已知每個騎士的仇人不超過n－1個，證明：摩爾林(亞瑟王的謀士)能夠讓這些騎士圍著圓桌坐下，使每個騎士都不與他的仇人相鄰．例11．有n人聚會，已知每人至少認識其中的[eq\f(n,2)]個人．而對任意的[eq\f(n,2)]個人，或者其中有兩人認識，或者余下的n－[eq\f(n,2)]人中有兩人相識．證明：當(dāng)n≥6時，這n個人中必有3人兩兩認識．例12⑴在有7個頂點的簡單圖中，沒有四邊形的圖的邊數(shù)n的最大值是多少？若能找到四個頂點A、B、C、D，且連了線段AB、BC、CD、DA，即是四邊形ABCD)．⑵(中國數(shù)學(xué)奧林匹克，1992)在有8個頂點的簡單圖中，沒有四邊形的圖的邊數(shù)n的最大值是多少？若能找到四個頂點A、B、C、D，且連了線段AB、BC、CD、DA，即是四邊形)

例13．若任意133個正整數(shù)中，至少有799對數(shù)互素，證明：其中必存在4個正整數(shù)a、b、c、d，使得a與b，b與c，c與d，d與a互素．練習(xí)題：1．平面上給定7個點，用一些線段連接它們，每三個點中至少有兩點相連，問至少要有多少條線段？試給出一個圖．2．20名選手參加14場單打比賽，每名選手都至少參加過1場．證明：必有某6場比賽的參賽者是12名不同的選手．3．有3n+1人，每兩人之間下象棋、圍棋、跳棋中的一種．已知每個人都與n個人下象棋，n個人下圍棋，n個人下跳棋．證明：其中必有3人，兩人下象棋，兩人下圍棋，兩人下跳棋．4．九名數(shù)學(xué)家出席一次國際會議，其中任意3人中至少有2人能講同一種語言．如果每位數(shù)學(xué)家至多能講3種語言．證明：至少有3位數(shù)學(xué)家能用同一種語言交談．5．證明：任意的9個人中，必有3個人互相認識或4個人互相不認識．6．⑴在一所房子里有10個人，其中任意3人中至少有2人互相認識，證明：其中有4人，他們?nèi)我?人都互相認識．⑵如果把⑴中的數(shù)10改為9，結(jié)論仍成立否？7．⑴試說明，存在無3點共線的6個點，它們之間連了12條線段，但其中沒有K4．⑵試證明：無3點共線的6個點之間連了13條線段，其中必有4個K4．8．某鎮(zhèn)有居民1000人，每人每天把昨天聽到的消息告訴自己認識的人，已知任何消息只要鎮(zhèn)上有人知道，都會經(jīng)過這樣的方式逐漸地為全鎮(zhèn)的人所知道．證明可以選出90名代表，使得同時向他們報告一個消息，經(jīng)過10天，這一消息就為全鎮(zhèn)的人知道．9．求滿足下列條件的最小正整數(shù)n：在圓周上任取n個點A1、A2、…、An，則在Ceq\o(\s\up5(2),\s\do3(n))個角∠AiOAj(1≤i＜j≤n)中，至少有2007個不超過120°．10．某次體育比賽，每兩名選手賽一場，無平局．通過比賽確定優(yōu)秀選手．設(shè)A為選手，如果對其他任意選手B，要么A勝B，要么存在選手C，使得A勝C，C勝B，則A即是優(yōu)秀選手．證明：如果按上述規(guī)則選出的優(yōu)秀選手只有1名，則這名選手勝其他所有的選手．11．凸n邊形及其n－3條在形內(nèi)不相交的對角線組成的圖形稱為一個剖分圖．證明：當(dāng)且僅當(dāng)n是3的倍數(shù)時，存在一個剖分圖是一個可以一筆畫的圈．12．已知n(n≥6的偶數(shù))人中任何3人之間至少有兩人互通電話，且每人至多與eq\b\bc\[(\f(n－2,2))個人互通了電話，證明：這n個人總可以分成不相交的兩組，使同一組內(nèi)任何兩人互通了電話．13．給定平面上無三點共線的n個點，以這n個點為兩個端點連出了m條線段，已知對于其中任意的兩點A、B，都有一個點C，使C與A、B都連有線段．求m的最小值．14．平面內(nèi)是否存在一個含n(n≥8)個點的圖，在這n個點間連有一些線段，使得從n個點出發(fā)的線段數(shù)分別為4，5，6，…，n－5，n－4，n－3，n－2，n－2，n－2，n－1，n－1，n－1?15．某團體中任意兩個認識的人都沒有共同的熟人，而任意兩個不認識的人都恰有兩個彼此共同的熟人．證明：該團體中每個人認識的人數(shù)都相同．16．由n個點和這些點之間的l條連線段組成一個空間圖形，其中n=q2＋q＋1，l≥eq\f(1,2)q(q＋1)2＋1，q≥2，q∈N．已知此圖中任四點不共面，每點至少有一條連線段，存在一點至少有q＋2條連線段．證明：圖中必存在一個空間四邊形(即由四點A、B、C、D和四條連線段AB、BC、CD、DA組成的圖形)．(2004年全國聯(lián)賽題)

圖論問題選講由若干個不同的點及連接其中某些點對的線所組成的一種圖形就稱為圖．圖中的點的集合，稱為圖的點集，記為V：V＝{v1，v2，…，vn，…}；圖中的線的集合，稱為圖的線集，記為E：E＝{vivj}(vi，vj∈V)．故一個圖由其點集V和線集E所決定，若用G表示圖，則記為G＝G(V；E)．含有n個點(|v|＝n，記號|M|表示有限集M中元素的個數(shù)，稱為濃度)的圖稱為n階圖．n階圖中共有Ceq\o(\s\up5(2),\s\do3(n))個點對，每對點有鄰接或不鄰接兩種可能情形，故點集為V＝{v1，v2，v3，…，vn}的n階圖共有2eq\s\up5(C\o(\s\up3(2),\s\do2(n)))個．在一個圖中，如果某點V共連了k條線，則說此點的“次數(shù)”(或“度數(shù)”)為k，記為degV＝k．線數(shù)最多的p階圖(即每個點對都連了1條線，共連出了Ceq\o(\s\up5(2),\s\do2(p))條線)稱為p階完全圖，通常記為Kp，如果一個n階圖的每個點的度數(shù)均等于r，則稱之為n階r度正則圖．例1．空間6點，無3點共線，每兩點連1條線，染紅或藍．⑴求證：必存在1個以其中三點為頂點的三角形．三邊同色；⑵求證：必存在2個以其中三點為頂點的三角形．三邊同色．證明：只證第⑵題：設(shè)這6個點各連出了di(i＝0，1，2，…，5)條紅線及5－di條藍線，則它們組成了di(5－di)個異色角．di(5－di)＝0，4，6．即di(5－di)≤6．從而圖中的異色角≤6×6＝36個．由于一個三角形，若為同色三角形，則異色角數(shù)＝0，若不是同色三角形，則異色角數(shù)＝2．于是異色三角形數(shù)≤eq\f(36,2)＝18．由于共有Ceq\o(\s\up5(2),\s\do2(6))＝20個三角形．故至少有2個同色三角形．⑶空間5點，無3點共線，每兩點連1條線，染紅或藍，是否一定存在1個以其中三點為頂點的三角形．三邊同色？解：不一定，如圖，五邊形ABCDE中，染了5條紅邊5條藍邊，其中沒有同色三角形．⑷把數(shù)1，2，3，4，5任意分成兩組，試證明：在這兩組數(shù)中，總有一組數(shù)中存在兩個數(shù)，它們的差(的絕對值)也在這一組中．解：任取6個點，分別標(biāo)上1，2，3，4，5，6．每兩點連一條線，并在這條線上注上這兩點差的絕對值．就得到一個K4，且每條線上所注數(shù)字只能是1，2，3，4，5．若數(shù)1，2，3，4，5已分成了A、B兩組，某條線上的數(shù)分入了A組，則把這條線染紅，分入了B組，則相應(yīng)的線染藍，由于K6的線二染色，必出現(xiàn)同色三角形，即該同色三角形上的三個數(shù)分入了同一組，設(shè)這個同色三角形的三個頂點的數(shù)為a、b、c(a＞b＞c)，則三條線上的數(shù)為a－b，b－c，a－c．于是a－b，b－c，a－c分入同一組，即這三個數(shù)滿足題目要求．例2．6人相互認識或相互不認識，只有當(dāng)其中4人圍坐一圈，相鄰2人都互相認識或都互相不認識時，這4人才能坐在一起打牌，問能否找到4人，這4人能夠在一起打牌．分析本題即：把K6的邊染成兩種顏色，是否一定存在一個同色四邊形．解用6個點表示這6個人，如果其中某兩個人互相認識，則在表示這兩個人的點之間連一條紅線，否則即連一條藍線．每點連出5條線，其中必有一種顏色線≥3條，即或紅線≥3條或藍線≥3條．把連出紅線≥3條的點稱為A類點，連出藍線≥3條的點稱為B類點，則A類點或B類點中必有一類的點數(shù)≥3，不妨設(shè)A類點數(shù)≥3，且v1，v2，v3為A類點，⑴設(shè)v1，v2間連藍線：由于v1，v2都連出了至少3條紅線，故其余4點中都分別有3點與此2點連了紅線，于是其余4點中必有2點與v1，v2都連紅線，不妨設(shè)v3，v4與v1，v2都連了紅線，則v1，v3，v2，v4四點連出同色四邊形．(圖1)⑵設(shè)v1，v2，v3之間都連紅線．由于v1，v2，v3的每一個都至少連出了3條紅線，故它們每一個都要與v4，v5，v6中的至少一個連紅線．①若v4，v5，v6中有某一點與此三點中的某兩點都連紅線，例如v4與v1，v2都連紅線，則v1，v3，v2，v4這4點連出同色四邊形．(圖2)②若v4，v5，v6中的每個點都只與v1，v2，v3這三點中的某一點連紅線，如圖3，則在其余的線中只要有任一條線連紅線，就有紅色四邊形出現(xiàn)．③若v4，v5，v6中的每一點與v1，v2，v3這三點中的某一點連紅線，而所有其余的線都是藍線，則出現(xiàn)藍色四邊形．(圖4)例3．給定空間中的9個點，任意4點不共面，每兩點間連一線段．求最小的n值，使當(dāng)對其中任意n條線段用紅、藍兩色之一任意染色時，都一定出現(xiàn)一個三邊同色的三角形．分析：6個點間共連15條線段，二染色，必有同色三角形．添上3個點就是9點，從9點中去掉3點，只要去掉的點少連1條線即去掉，9個點之間兩兩連線有Ceq\a(2,9)＝36條，因此去掉3條即是去掉3點，染色線段應(yīng)有33條，即n=33．解：設(shè)染色的線段至少有33條，則因9個點之間兩兩連線有Ceq\a(2,9)＝36條，故不染色的線段至多有3條．設(shè)點A引出不染色的線段，則去掉點A及所引出的線段．在剩下的點及線段中，若還有點B引出不染色的線段，同樣地再將B及引出的線段去掉，依次進行．因不染色的線段至多3條，所以至多去掉3個頂點，則還剩下6個頂點，其兩兩連線都染上了紅色或藍色．即得到k6（6階完全圖）圖的2-染色．熟知，存在同色三角形．其次，存在一個9頂點32條邊的圖，把圖的邊2－染色，可使圖中無同色三角形．如圖所示，將9個點分成5組A＝{V1，V2}、B＝{V3，V4}、C＝{V5，V6}、D＝{V7，V8}、E＝{V9}，兩組間連一條紅線表示從這兩組中任取一點都連有紅線；兩組間連一條藍線表示從這兩組中任取一點都連有藍線；每一組內(nèi)部的點之間不連線．該圖構(gòu)成有9個頂點，有Ceq\a(2,9)－4＝32條邊，且不存在2－染色的同色三角形．從而，欲求的最小n值為33．例4．給定平面上的點集P={P1，P2，…，P1994},P中任三點均不共線，將P中的所有的點任意分成83組，使得每組至少有3個點，且每點恰好屬于一組，然后將在同一組的任兩點用一條線段相連，不在同一組的兩點不連線段，這樣得到一個圖案G，不同的分組方式得到不同的圖案，將圖案G中所含的以P中的點為頂點的三角形個數(shù)記為m(G)．(1)求m(G)的最小值m0．(2)設(shè)G*是使m(G*)=m0的一個圖案，若G*中的線段(指以P的點為端點的線段)用4種顏色染色,每條線段恰好染一種顏色．證明存在一個染色方案,使G*染色后不含以P的點為頂點的三邊顏色相同的三角形．解：設(shè)G中分成的83個子集的元素個數(shù)分別為ni(1≤i≤83)，eq\o(\s\up12(83),\s\do5(Σ),\s\do12(i=1))ni=1994．且3≤n1≤n2≤…≤n83．則m(G)=eq\o(\s\up12(83),\s\do5(Σ),\s\do12(i=1))Ceq\o(\s\up4(3),\s\do3(ni))．即求此式的最小值．設(shè)nk+1>nk＋1．即nk+1－1≥nk＋1．則Ceq\o(\s\up4(3),\s\do3(ni+1))+Ceq\o(\s\up4(3),\s\do3(ni+1－1))－(Ceq\o(\s\up4(3),\s\do3(ni))+Ceq\o(\s\up4(3),\s\do3(ni+1)))=Ceq\o(\s\up4(2),\s\do3(ni))－Ceq\o(\s\up4(2),\s\do3(ni+1))＜0．這就是說，當(dāng)nk+1與nk的差大于1時，可用nk+1－1及nk+1代替nk+1及nk，而其余的數(shù)不變．此時，m(G)的值變?。谑强芍?，只有當(dāng)各ni的值相差不超過1時，m(G)才能取得最小值．1994=83×24+2．故當(dāng)81組中有24個點，2組中有25個點時，m(G)達到最小值．m0=81Ceq\a(3,24)+2Ceq\a(3,25)=81×2024+2×2300=168544．⑵取5個點為一小組，按圖1染成a、b二色．這樣的五個小組，如圖2，每個小圓表示一個五點小組．同組間染色如圖1，不同組的點間的連線按圖2染成c、d兩色．這25個點為一組，共得83組．染色法相同．其中81組去掉1個點及與此點相連的所有線．即得一種滿足要求的染色．鏈：若在一個圖G＝(V；E)中取n＋1個頂點v1、v2、…、vn+1，每兩個相鄰的頂點vi、vi+1間連有一條邊li，則邊l1，l2，…，ln就稱為從v1到vn+1的一條鏈，n稱為鏈的長度．一條鏈的兩個端點v1與vn+1重合時，就稱為圈．如果圖G的任何兩個頂點之間都有一條鏈，就說這個圖是連通的，否則就是不連通的．頂點的次數(shù)為奇數(shù)，則稱此頂點為奇頂點。當(dāng)頂點的次數(shù)為偶數(shù)時，就稱此頂點為偶頂點．任何圖的奇頂點個數(shù)為偶數(shù)．圖G是一筆畫的充分必要條件是G是連通的有限圖，其奇頂點的個數(shù)為0或2．并且當(dāng)且僅當(dāng)奇頂點的個數(shù)為0時，連通圖G是一個圈．沒有圈的連通圖稱為樹．⑴如果樹T的頂點數(shù)為n，則其邊數(shù)為n－1．⑵如果圖G是連通的，且有n個頂點與n－1條邊，則G是一個樹．樹T具有以下性質(zhì)：⑴在T中去掉任一邊后，所得的圖是不連通的；⑵在T中添上1條邊后，所得的圖有圈；⑶T中的任兩個頂點v1與v2間有且僅有1條鏈．例5．在88棋盤的方格中分別填寫1，2，…，82，每格一個數(shù)．證明：必有兩個相鄰方格(有公共邊的方格)，方格中的兩個數(shù)的差至少為5．⑴證：取每個方格的中心，凡是相鄰的兩個方格，就把相應(yīng)的中心連一條線．這樣得到了一個圖G(圖中紅線組成的圖即為圖G)．圖G的的直徑=14，，故圖G中任意兩點的距離≤14．若相鄰兩個方格中填的數(shù)相差＜5，則差≤4，于是圖G中所填兩個數(shù)的差≤14×4＝56．但圖中填了1與64，此二數(shù)必有一條鏈相連，此鏈的長≤14．即其差≤56，與64－1＝63矛盾．下面兩題其實是同一個意思，不過用兩種不同的方法給予證明而已．例6．⑴證明：有n個頂點且不含三角形的圖G的最大邊數(shù)為eq\b\bc\[(\f(n2,4))．證明：設(shè)v1是G中具有最大度數(shù)的頂點，d(v1)＝d．又設(shè)與v1相鄰的d個頂點為vn，vn－1，…，vn－d＋1．由于G不含三角形，所以vn，vn－1，…，vn－d＋1均互不相鄰．故G的邊數(shù)e≤(n－d)d≤eq\f(n2,4)．由于G的邊數(shù)為整數(shù)，故e≤eq\b\bc\[(\f(n2,4))．當(dāng)n＝2m時，取二部圖G＝Km，m．當(dāng)n＝2m＋1時，取二部圖G＝Km＋1，m．即滿足e＝eq\b\bc\[(\f(n2,4))．⑵設(shè)Z為空間含有n(n≥4)個點的點集，其中任意四點不共面，這些點之間連有eq\b\bc\[(\f(n2,4))＋1條線段．證明：這些線段必可構(gòu)成兩個有公共邊的三角形．(當(dāng)n為偶數(shù)時的情況即是1987年國家集訓(xùn)隊選拔考試題)證明：n＝4時，Z中共有4個點，共連有5條線段，由于4點間共可連6條線段，共組成4個三角形．每條線段與不在其上的兩點各可組成一個三角形，故去掉任一條線段，則減少2個三角形．即4點連5條線段必連出兩個有公共邊的三角形．n＝5時，Z中5個點連eq\b\bc\[(\f(52,4))＋1＝7條線段，必有一點連線段數(shù)不超過2條(如果每點連線段數(shù)≥3，則統(tǒng)計每點的連線數(shù)的和≥35＝15條，由于每條被統(tǒng)計了2次，應(yīng)是27＝14條)．去掉連線數(shù)不超過2條的點及其所連線段，則至多去掉2條線段，余下4點至少連了5條線段，如上證，必有兩個有公共邊的三角形．設(shè)n＝k(k≥4)時，命題成立．當(dāng)n＝k＋1時，由于統(tǒng)計各點連出線段數(shù)的和＝2eq\b\bc\[(\f((k＋1)2,4))＋2．則連線數(shù)最少的點A，則點A的連線數(shù)≤eq\f(1,k＋1)eq\b\bc\((2\b\bc\[(\f((k＋1)2,4))＋2)．當(dāng)k＝2t時，eq\b\bc\[(\f((k＋1)2,4))＝t(t＋1)．eq\f(1,k＋1)eq\b\bc\((2\b\bc\[(\f((k＋1)2,4))＋2)＝eq\f(1,2t＋1)(2t2＋2t＋2)＝t＋eq\f(t＋1,2t＋1)．即該點連線段數(shù)≤t．此時，去掉點A及所連之線段，則余下k個點，且余下線段數(shù)≥t2+1＝eq\b\bc\[(\f(k2,4))+1．當(dāng)k＝2t－1時，eq\b\bc\[(\f((k＋1)2,4))＝t2．eq\f(1,k＋1)eq\b\bc\((2\b\bc\[(\f((k＋1)2,4))＋2)＝eq\f(1,2t)(2t2＋2)＝t＋eq\f(1,t)．即該點連線段數(shù)≤t．此時，去掉點A及所連之線段，則余下k個點，且余下線段數(shù)≥t2－t＋1＝eq\b\bc\[(\f((2t－1)2,4))＋1＝eq\b\bc\[(\f(k2,4))＋1．于是，由歸納假設(shè)可知，余下點及線段中，必有兩個有公共邊的三角形．綜上可知，命題成立．例7．S為m個無序正整數(shù)對(a，b)(即(a，b)與(b，a)是相同的)(1≤a，b≤n，a≠b)組成的集合．證明：至少有eq\f(4m,3n)(m－eq\f(n2,4))個三元數(shù)組(a，b，c)，適合：(a，b)，(b，c)，(c，a)都屬于S．證明：作一個圖G＝(V，E)，以點vi表示數(shù)i(i＝1，2，…，n)，當(dāng)且僅當(dāng)(i，j)∈S時，在點vi與vj間連1條線段．于是圖G有n個頂點，m條邊．問題轉(zhuǎn)化為：圖G中至少有eq\f(4m,3n)(m－eq\f(n2,4))個三角形．令頂點vi的度為di，取G的任一條邊vivj，則vi與vj共向其余的頂點引出d1＋d2－2條邊．從而共有di＋dj－n對分別由vi與vj引向同一頂點的線段，與vivj組成三角形．因此G中至少有di＋dj－n個以vivj為一邊的三角形．但這個三角形在G三邊上被計數(shù)了3次．從而G中三角形數(shù)k滿足k≥eq\f(1,3)eq\o(\s\do3(Σ),\s\do10(vivj∈E))(di＋dj－n)．注意到di在上述和式中出現(xiàn)了di次，而G中共有m條邊，故k≥eq\f(1,3)(eq\o(\s\do3(Σ),\s\do10(i＝1),\s\up10(n))deq\o(\s\do2(i),\s\up5(2))－mn)．由于eq\o(\s\do3(Σ),\s\do10(i＝1),\s\up10(n))di＝2m，故neq\o(\s\do3(Σ),\s\do10(i＝1),\s\up10(n))deq\o(\s\do2(i),\s\up5(2))≥(eq\o(\s\do3(Σ),\s\do10(i＝1),\s\up10(n))di)2＝4m2eq\o(\s\do3(Σ),\s\do10(vivj∈E))deq\o(\s\do2(i),\s\up5(2))≥eq\f(4m2,n)．∴k≥eq\f(1,3)(eq\f(4m2,n)－mn)＝eq\f(4m,3n)(m－eq\f(n2,4))．說明：由本題也可看出m≤eq\f(n2,4)時，k可能為0．例8．十個學(xué)生參加一次考試，試題共有十道，已知沒有兩個學(xué)生做對的題目完全相同，證明：這十道題中可以找到一道題，把這道題取消后，每兩個學(xué)生所做對的題目仍不會全同．(假定每個題，都只有做對與做錯這兩種情況，沒有部分對的情況發(fā)生)證明反設(shè)取消任何一題后，都有兩個學(xué)生做對的題目完全相同．首先，取消某一題后，全同的人不會多于2人，否則，由于每道題的結(jié)果都只有全對或全錯兩種情況，在取消某題前，這題必有至少兩人答的情況相同，于是，取消這題前，就有兩人答對的情況全同．用10個點表示這10個學(xué)生，如果取消某題后有某兩人的對錯情況全同，則在表示這兩人的兩個點間連一條線，并在線旁注上該題的題號(如果有幾對人全同，則只任取其中一對連線注題號)．這樣，在10個點間就連了10條線，于是必出現(xiàn)圈．現(xiàn)取出現(xiàn)的一個圈，從該圈的任一頂點出發(fā)，沿圈走一圈回到起點，由于每經(jīng)過一條邊，到新一個頂點時，都與原頂點有一個題目的差異，且經(jīng)過不同的邊，對錯的題目不同．這樣回到原起點時，對錯的情況不可能還原，這就引出矛盾．(例如v1與v2間連線上注的題號為1，則若v1第一題正確，則v2第一題錯誤，后面的邊上都沒有注題號1，故以后每個vi的第1題對錯情況都不變，即，第1題都錯．到沿此圈前進一圈回到v1，應(yīng)得v1的第一題錯，與初始狀態(tài)的假定“第1題正確”矛盾．例9．n名兒童希望把m塊形狀為矩形的相同的巧克力分成重量相等的n份(n，m∈N*)．規(guī)定每塊巧克力至多被分成兩塊．對怎樣的n與m，上述要求能實現(xiàn)？解：如果m≥n，則每人分得的巧克力不少于1塊，這總是可以按上述要求分成的．m＝n時，每人1塊巧克力，不要分開，當(dāng)m＞n時，設(shè)每塊巧克力的長度為l，把這m塊巧克力長邊相連排成一排，其總長度為ml，再按長度分成n等分，每份長為eq\f(ml,n)，每名兒童取1份，由于eq\f(m,n)＞1，故每塊巧克力至多分成了兩塊，滿足題意．當(dāng)m＜n時，eq\f(m,n)＜1，于是每塊巧克力都要被切開．如果eq\f(m,n)＜eq\f(1,2)，顯然不能按要求能分成；當(dāng)eq\f(m,n)＝eq\f(1,2)時，只要把每塊巧克力二等分即可得到滿足要求的分法；當(dāng)eq\f(1,2)＜eq\f(m,n)＜1時．用n個點表示這n名兒童，若某兩人各取了同一塊巧克力的兩部分，就在表示相應(yīng)的人的點間連一條線．這就得到了一個圖．若此圖有k個連通分支．每個分支分別有m1、m2、…、mk條邊與n1、n2、…、nk個頂點，由于每個兒童分得的巧克力相等，故eq\f(m1,n1)＝eq\f(m2,n2)＝…＝eq\f(mk,nk)＝eq\f(m,n)．因每個連通分支是頂點數(shù)多于邊數(shù)的連通圖，所以必有mi＝ni－1(i＝1，2，…，k)．于是，n1＝n2＝…＝nk＝eq\f(n,k)，m1＝m2＝…＝mk＝eq\f(m,k)，因此，可以分的一個必要條件是：存在m、n的一個公約數(shù)k，使eq\f(m,k)＝eq\f(n,k)－1，即m＝n－k．這個條件也是充分的．首先，當(dāng)k＝1時，因為每個兒童分得一塊巧克力的eq\f(n－1,n)，可以把每塊巧克力切成eq\f(n－1,n)與eq\f(1,n)的兩塊，前m－1名兒童每個人取eq\f(n－1,n)，最后一名兒童取n－1個eq\f(1,n)即可．對于k＞1，可以把每塊巧克力切成eq\f(n－k,n)與eq\f(k,n)的兩塊，前m－k名兒童每個人取eq\f(n－k,n)，后k名兒童取eq\f(m,k)個eq\f(k,n)，此時后k名兒童取eq\f(m,k)×eq\f(k,n)＝eq\f(m,n)＝eq\f(n－k,n)．于是每人分得的巧克力數(shù)相等．例10．亞瑟王(傳說中的英國國王)在王宮中召見他的2n名騎士，其中某些騎士之間互相有仇，已知每個騎士的仇人不超過n－1個，證明：摩爾林(亞瑟王的謀士)能夠讓這些騎士圍著圓桌坐下，使每個騎士都不與他的仇人相鄰．證明：如果兩人不是仇人，就稱這兩人為朋友．把這2n個人任意排列成一圈，如果相鄰兩人是朋友，就把他們連一條線．這時這個圈就斷成若干段．從某一人出發(fā)，順時針檢查，遇到第一個斷開的地方，例如相鄰的A1與B1間斷開．現(xiàn)從B1下面的人開始檢查每個A1的朋友：必能找到相鄰兩人A2、B2，其中A1與A2是朋友，B1與B2也是朋友．若每個與A1是朋友的人后面的人都是B1的仇人，由于A1的朋友至少有n個，而B1的仇人不超過n－1個，從而每個A1的朋友后面的人不可能都是B1的仇人．即這樣的兩個人是能找到的．現(xiàn)在把此圓周上從B2順時針向后直到A1的一段不動，而把從B1到A2的一段保持相鄰關(guān)系翻轉(zhuǎn)，使A2轉(zhuǎn)到A1后面而B1轉(zhuǎn)到B2前面．這樣，除A1、A2及B1、B2由原來不相鄰變?yōu)橄噜復(fù)馄溆嗟娜说南噜応P(guān)系沒有改變，而此時原來A1B1斷開之處已被A1A2由于圓圈上斷開處只有有限處，而每經(jīng)過這樣一次調(diào)整可以使斷開處減少1處．故經(jīng)過有限次調(diào)整，就能得到滿足要求的坐法．例11．有n人聚會，已知每人至少認識其中的[eq\f(n,2)]個人．而對任意的[eq\f(n,2)]個人，或者其中有兩人認識，或者余下的n－[eq\f(n,2)]人中有兩人相識．證明：當(dāng)n≥6時，這n個人中必有3人兩兩認識．證明：作一個圖，用n個點表示這n個人，凡二人認識，則在表示此二人的點間連一條線．問題即，在題設(shè)條件下，存在以這n點中的某三點為頂點的三角形．設(shè)點a連線條數(shù)最多，在與a連線的所有點中點b連線最多，與a連線的點除b外的集合為A，與b連線的點除a外的集合為B．1°設(shè)n=2k，則每點至少連k條線，A、B中都至少有k－1個點．⑴若存在一點c，與a、b都連線，則a、b、c滿足要求；⑵若沒有任何兩點與a、b二點都連線(圖1)，則由A∩B=?，|A∪B|≤2k－2，|A|≥k－1，|B|≥k－1，故得|A|=|B|=k－1，且圖中每點都連k條線．若A中任何兩點間均未連線，B中任兩點也未連線，則A∪中不存在兩點連線，B∪{a}中也不存在兩點連線．與已知矛盾(與“對任意的[eq\f(n,2)]個人，或者其中有兩人認識，或者余下的n－[eq\f(n,2)]人中有兩人相識”矛盾)．故在A(或B)中必存在兩點，這兩點間連了一條線，則此二點與a(b)連出三角形，2°設(shè)n=2k+1．則每點至少連k條線，A、B中都至少有k－1個點．⑴若存在一點c，與a、b都連線，則a、b、c滿足要求；⑵若沒有任何兩點與此二點都連線，且|A|≥k，則由|B|≥k－1時(圖2)，則由A∩B=?，|A∪B|≤2k－1，|A|≥k，|B|≥k－1，故得|A∪B|=2k－1，|A|=k，|B|=k－1，若A中任何兩點間均未連線，B中任兩點也未連線，則A∪中不存在兩點連線，B∪{a}中也不存在兩點連線．與已知矛盾．故A(或B)中存在兩點，這兩點間連了一條線，則此二點與a連出三角形，⑶若沒有任何兩點與此二點都連線，且|A|=k－1，即每點都只連k條線．這時，必有一點與a、b均未連線，設(shè)為c．c與A中k1個點連線，與B中k2個點連線，k1+k2=k，且1≤k1，k2≤k－1．否則若k2=0，則A∪中各點均未連線，B∪{a，c}中各點也未連線．矛盾．故k1，k2≥1．且由于n>6，即k1，k2中至少有一個≥2，不妨設(shè)k1≥2，現(xiàn)任取B中與c連線的一點b1，由于b1與B中其余各點均未連線，若b1與A中的所有與c連線的點均未連線，則b1連線數(shù)≤2+k－1－k1≤k－1，矛盾，故b1至少與此k1個點中的一點連線．故證．例12⑴在有7個頂點的簡單圖中，沒有四邊形的圖的邊數(shù)n的最大值是多少？若能找到四個頂點A、B、C、D，且連了線段AB、BC、CD、DA，即是四邊形ABCD)．解：連一個七邊形，如圖再從一點連2條對角線組成兩個三角形，則不出現(xiàn)四邊形．即n≥9．①若有4點間連了5條線，則必有四邊形；由于4點連6線，共有3個四邊形(1，2相鄰：1－2－3－4與1－2－4－3，1，2相對：1－3－2－4)，去掉1條線則去掉了2個四邊形，從而必有四邊形．②若點v與v1~vk均連線，而vk＋1與v1~vk中的兩點都連線，則存在四邊形．當(dāng)n＝10時，7點連10條線，共有20度，故其中最大的度d≥3．⑴d＝3，設(shè)v1與v2、v3、v4連線，與v5，v6，v7未連線．則若{v2，v3，v4}中某點的度≥2，則出現(xiàn)四邊形．若圖中沒有四邊形，則{v2，v3，v4}內(nèi)部至多連1條線，{v5，v6，v7}內(nèi)部至多連3條線，{v5，v6，v7}中每一點向{v2，v3，v4}至多連1條線，即至多連3條線．由于3＋1＋3＋3＝10，故上述“至多”全部應(yīng)改為“恰好”．即{v2，v3，v4}內(nèi)部恰好連1條線，例如v2v3，{v5，v6，v7}中兩兩連線，且其中每點向{v2，v3，v4}連1條線．故出現(xiàn)四邊形(兩點向同一點連線或每點各向一點連線)．⑵d＝4．設(shè)v1與{v2，v3，v4，v5}連線，若{v2，v3，v4，v5}中某點的度≥2，必出現(xiàn)四邊形．故其中每點的度≤1，則其內(nèi)部至多連2條線．{v6，v7}中至多連1條線，{v6，v7}向{v2，v3，v4，v5}至多連2條線(若連了3條線，則必從v6或v7向{v2，v3，v4，v5}中連了2條線，出現(xiàn)四邊形)，4＋2＋1＋2＜10．矛盾．⑶d≥5，與v1相連的點的集合為A，A內(nèi)部至多連2條線，不與v1相連的點集為B，|B|＝1或0，仍有連線數(shù)＜9．矛盾．⑵(中國數(shù)學(xué)奧林匹克，1992)在有8個頂點的簡單圖中，沒有四邊形的圖的邊數(shù)n的最大值是多少？若能找到四個頂點A、B、C、D，且連了線段AB、BC、CD、DA，即是四邊形)解：連一個八邊形，如圖再連3條對角線，則不出現(xiàn)四邊形(右圖是其同構(gòu)圖)．設(shè)八點連了12條線．共有24度，記d1，d2，…，d8為八個頂點的度，其最大值為d．則d≥3．d1＋d2＋…＋d8＝24．①若有4點間連了5條線，則必有四邊形；由于4點連6線，共有3個四邊形(1，2相鄰：1－2－3－4與1－2－4－3，1，2相對：1－3－2－4)，去掉1條線則去掉了2個四邊形，從而必有四邊形．②若點v與v1~vk均連線，而vk＋1與v1~vk中的兩點都連線，則存在四邊形．⑴d=3，此時，每個頂點的度均為3．設(shè)v1與v2、v3、v4連線，與v5，v6，v7，v8未連線．若{v2，v3，v4}中某點的度≥2，則出現(xiàn)四邊形．若圖中沒有四邊形，則則{v2，v3，v4}內(nèi)部至多連1條線，{v5，v6，v7，v8}內(nèi)部至多連4條線，{v5，v6，v7，v8}中每一點向{v2，v3，v4}至多連1條線，即至多連4條線．由于3＋1＋4＋4＝12，故上述“至多”全部應(yīng)改為“恰好”．即{v2，v3，v4}內(nèi)部恰好連1條線，例如v2v3，則v4要與{v5，v6，v7，v8}中的兩點連線，例如v4v5，v4v6，而v7、v8與v2，v3各連了1條線，所以，{v5，v6，v7，v8}中每點的度都是2，能一筆畫出．即存在四邊形．⑵d＝4，設(shè)v1與{v2，v3，v4，v5}連線，若{v2，v3，v4，v5}中某點的度≥2，必出現(xiàn)四邊形．若其中每點的度≤1，則其內(nèi)部至多連2條線．{v6，v7，v8}內(nèi)部至多3邊，{v2，v3，v4，v5}與{v6，v7，v8}之間至多連3邊(否則連4邊，{v6，v7，v8}中必有某點向{v2，v3，v4，v5}中連了2條線，出現(xiàn)四邊形(情形②)．由4＋2＋3＋3＝12，故上述“至多”應(yīng)為“恰好”．這時圖中出現(xiàn)三個三角形，如v1v2v3，v1v4v5與v6v7v8，且{v6，v7，v8}中每點至多向{v2，v3，v4，v5}中一點連線，于是{v2，v3}與{v4，v5}中必有某一個與{v6，v7，v8}中的兩點連線，出現(xiàn)四邊形．⑶d＝5．與v1相連的有5個點，{v2，v3，v4，v5，v6}，記為A，不與v1相連的有2個點，{v7，v8}記為B．即B中至多連1條線．A內(nèi)至多連2條線．于是A與B中點至少連4條線，設(shè)A中v2v3，v4v5連線，則{v2，v3}，{v4，v5}，{v6}中必有某一個與{v7，v8}連2條線，若是{v2，v3}或{v4，v5}與{v7，v8}中連了2條線，則出現(xiàn)四邊形，若與v6連2條線，但v7、v8還要與{v2，v3}，{v4，v5}連2條線，仍出現(xiàn)四邊形(圖右的(1286)或(1476))．⑷d＝6或7，與v1相連的有d個點，記為A，不與d相連的7－d個點，記為B，此時A內(nèi)至多連3條線，B中沒有線，故B中與A中至少連2條線，必出現(xiàn)四邊形．例13．若任意133個正整數(shù)中，至少有799對數(shù)互素，證明：其中必存在4個正整數(shù)a、b、c、d，使得a與b，b與c，c與d，d與a互素．分析：133個點，某些點間連了線，且至少連了799條線．則其中至少連出了一個四邊形．799＝1336＋1．證明：用133個點表示這133個數(shù)，若某兩個數(shù)互素，就在表示這兩個數(shù)的點間連一條線段．設(shè)從點Ai出發(fā)的線段有di條，則eq\o(\s\do7(i＝1),\s\up11(133),∑)di≥2799．若兩個點A、B都與點C連了線，就稱A、B是屬于C的點對．于是分別屬于Ai(i＝1，2，…，133)的點對的總和為M＝eq\o(\s\do7(i＝1),\s\up11(133),∑)Ceq\o(\s\up4(2),\s\do3(di))＝eq\f(1,2)eq\o(\s\do7(i＝1),\s\up11(133),∑)di(di－1)＝eq\f(1,2)eq\o(\s\do7(i＝1),\s\up11(133),∑)(deq\o(\s\up4(2),\s\do3(i))－di)≥eq\f(1,2)[eq\f((\o(\s\do7(i＝1),\s\up11(133),∑)di)2,133)－eq\o(\s\do7(i＝1),\s\up11(133),∑)di]＝eq\f(1,2133)(eq\o(\s\do7(i＝1),\s\up11(133),∑)di)(eq\o(\s\do7(i＝1),\s\up11(133),∑)di－133)≥eq\f(1,2133)2799(2799－133)＞eq\f(1,2133)26133(26133－133)＝eq\f(1211133,2)＝Ceq\o(\s\up4(2),\s\do3(133))．但這133個點間每兩點都連線時，點對數(shù)為Ceq\o(\s\up4(2),\s\do3(133))．而M＞Ceq\o(\s\up4(2),\s\do3(133))，說明上面的計數(shù)中有重復(fù)計數(shù)．即存在點A、C，它們既是屬于B的點對，又是屬于D的點對，即A，B；B，C；C，D；D，A都連了線．故證．又解：畫一個133×133表格，把這133個數(shù)記為A1，A2，…，An，若Ai與Aj互素，則將表格中第i行j列的方格中心涂紅．于是當(dāng)d(Ai)＝m時，則表格中的i行及i列各有m個紅點．且表格的主對角線上的方格中心都沒有涂紅，所以，表中共有2×799個紅點．若存在滿足題中條件的四個數(shù)，則表格中存在一個邊平行于格線的矩形，其四個頂點都為紅點．同行的兩個紅點組成一個紅點對，于是表中紅點對數(shù)為eq\o(\s\do7(i＝1),\s\up11(133),∑)Ceq\o(\s\up4(2),\s\do3(di))．若有不同兩行的各一個紅點對處于同一位置，則表格中存在四個頂點都為紅點且邊平行于格線的矩形．反設(shè)表格中任何四個紅點其中心都不是一個邊平行于格線的矩形頂點．則表格中紅點對數(shù)≤Ceq\o(\s\up4(2),\s\do3(133))．但由上證知eq\o(\s\do7(i＝1),\s\up11(133),∑)Ceq\o(\s\up4(2),\s\do3(di))＞Ceq\o(\s\up4(2),\s\do3(133))．故證．練習(xí)題：1．平面上給定7個點，用一些線段連接它們，每三個點中至少有兩點相連，問至少要有多少條線段？試給出一個圖．解：7個點中共有三點組Ceq\a(3,7)＝35個．每條線段共與其余5點組成5個三角形．故線段條數(shù)≥eq\f(35,5)＝7條．如果有一個點沒有連線，則其余6點兩兩都必須連線，要Ceq\a(2,6)＝15條．如果有一點只連了一條線，其余5點必須兩兩連線，連線數(shù)＞Ceq\a(2,5)＋1＝11條．設(shè)某點只連了2條線，如AB、AC連了2條線，則其余4點均未與A連線，于是它們必須兩兩互連，應(yīng)連Ceq\a(2,4)＝6條．此時，取B、C兩點及其余4點中的任一點，尚不滿足條件，故BC應(yīng)連線，此時連了9條線滿足題目要求．若每點都至少連出3條線，則總度數(shù)≥21，即至少連了[eq\f(21,2)]＋1＝11條線．∴至少連9條線．2．20名選手參加14場單打比賽，每名選手都至少參加過1場．證明：必有某6場比賽的參賽者是12名不同的選手．解：用20個點表示這20個人，若某兩人比賽過就在表示這兩人的點間連1條線，題意即：已連了14條線，每點至少連了1條線．求證：有6條線，連的12個點互不相同．設(shè)此20個點的度分別為d1，d2，…，d20，則d1+d2+…+d20=28．把度為di的頂點處連接的di－1條邊刪去．則至多刪去了(d1－1)+(d2－1)+…+(d20－1)=28－20=8條邊，于是還剩下6條邊，但每個頂點的度≤1．即此6條邊連接12個頂點．3．有3n+1人，每兩人之間下象棋、圍棋、跳棋中的一種．已知每個人都與n個人下象棋，n個人下圍棋，n個人下跳棋．證明：其中必有3人，兩人下象棋，兩人下圍棋，兩人下跳棋．解：即一個三色的K3n+1，每點都連出n條紅線，n條藍線及n條黃線．其中一定有一個三角形，三邊不同色．由一個頂點出發(fā)的兩條線組成的角如果邊的顏色不同，則稱為異色角．一個三角形如果三邊不同色，則其三個角都是異色角，稱為異色三角形．每個頂點處的異色角都有3n2個，從而這個K3n+1中的異色角共有3n2(3n＋1)個．由這些線段組成的三角形共有Ceq\a(3,3n+1)＝eq\f(1,6)(3n＋1)3n(3n－1)＝eq\f(1,2)n(3n＋1)(3n－1)個．∴由抽屜原理知，[eq\f(3n,eq\f(1,2)(3n－1))]＋1＝3，即至少存在一個三角形，有3個異色角，即為異色三角形．4．九名數(shù)學(xué)家出席一次國際會議，其中任意3人中至少有2人能講同一種語言．如果每位數(shù)學(xué)家至多能講3種語言．證明：至少有3位數(shù)學(xué)家能用同一種語言交談．證明：用9個點表示這9個人，任二人如能用第r種語言交談，則在表示此二人的點間連一條線并涂上第r種顏色，于是，本題即是證明，存在一個同色的三角形．首先，若v1與v2間連了第k種顏色線，v1與v3間也連了第k種顏色線，則v2與v3間也要連第k種顏色線．此時即出現(xiàn)同色的三角形．所以只要證明從其中某一點出發(fā)的線中必有兩條線的顏色相同．反設(shè)從任一點出發(fā)的線中沒有同色的線，由于每個人至多會用三種語言．即degvi≤3，于是v1至少與5個點不鄰接，設(shè)為v2、…、v6，同樣，v2至少與5個點不相鄰接，于是v3、…、v6中至少有一點與v2不相鄰．設(shè)為v3，于是v1、v2、v3不相鄰接．與已知矛盾．故證．又證：若每點的度均≤3，于是，必有兩點未連線，設(shè)v1、v2未連線，則其余各點均必須與這2點之一連線，否則若v3與v1、v2均未連線，則v1、v2、v3兩兩均未連線，矛盾，于是v1、v2與其余7點至少連了7條線，與degv1＋degv2≤6矛盾．所以，必存在某點的度≥4．由于這一點出發(fā)的線只有3種顏色，故必有2線同色，可證．5．證明：任意的9個人中，必有3個人互相認識或4個人互相不認識．即證明：在任意的K9中，把邊涂成紅或藍兩種顏色，則必存在紅色K3或藍色的K4．或：在一個有9個頂點的圖G中，必存在K3，或在其補圖中，存在K4．證明：⑴如果存在一個頂點，從這點出發(fā)的8條線中，有至少4條為紅色，設(shè)從v1引出的4條線為紅色，引到v2，v3，v4，v5．若此4點中的某2點間連了紅色線，則存在紅色K3，若此4點間均連藍線，則存在藍色K4．⑵如果從任一點出發(fā)的8條線中，紅色線都少于4條．于是從每點出發(fā)的藍色線都多于4條，即至少5條．但由于任何圖中的奇頂點個數(shù)為偶數(shù)，故不可能這9個頂點都引出5條藍線．于是至少有一個頂點引出的藍線≥6條，例如從v1到v2，v3，…，v7都引藍線，則在v2，v3，…，v7這6個點的圖中，必存在紅色三角形或藍色三角形，于是G中必有紅色K3，或藍色K4．6．⑴在一所房子里有10個人，其中任意3人中至少有2人互相認識，證明：其中有4人，他們?nèi)我?人都互相認識．⑵如果把⑴中的數(shù)10改為9，結(jié)論仍成立否？解：用10個點表示這10個人，如果某2人互相認識，則在表示這兩人的點間連1條線．即任3點都至少連了1條線，要求證明存在一個K4．設(shè)不存在K4，即任意4點中總有2點沒有連線，①設(shè)某一點A與4點都沒有連線，則由假設(shè)此4點中有2點未連線，則此2點與A共3點均未連線，與題設(shè)矛盾．故A至多與3點未連線，即至少與6點連了線．②設(shè)A與A1、A2、…，A6連線，則A1，…，A6中任意3點必有2點未連線，否則存在K4，③設(shè)A1與Bi、Bj、Bk都未連線，則Bi、Bj、Bk間若有兩點未連線，則出現(xiàn)3點，都未連線，與已知矛盾．故此三點間都連了線，于是此三點與A成為K4．④由③知A1，…，A6中任一點至多與其余5點中的2點未連線．即與其余5點中至少3點連了線．設(shè)A1與A2、A3、A4連了線．此時A2、A3、A4間至少連了1條線，設(shè)A2A3連了線，則A、A1、A2、A3成為K4由上證可知，不存在K4的假設(shè)不成立．⑵若有某點連出6條線，則如上證．若每點連線數(shù)<6，當(dāng)每點連線數(shù)都=5時．此時9個點連線統(tǒng)計為45，為奇數(shù)．不可能．若有某點連線數(shù)<5，即該點至少與4點未連線，則如上①，矛盾．從而必有點連線數(shù)=6的點．7．⑴試說明，存在無3點共線的6個點，它們之間連了12條線段，但其中沒有K4．⑵試證明：無3點共線的6個點之間連了13條線段，其中必有4個K4．解：把6個點平均分成3組，每組2個點，規(guī)定同組的點不連線，不同組的點都連線，則共連Ceq\o(\s\do2(6),\s\up5(2))－3＝12條線段，但任取其中4點，必有2點同組，這2點間沒有連線段，故不存在K4．⑵K6共有15條邊，現(xiàn)去掉2條邊后即有13條邊，分兩種情形：①去掉的兩邊有一個公共端點，如圖設(shè)v1v2，v2v3沒有連線，則去掉其公共端點v2，在其余5點中任取4點均為K4，即有4個K4；②去掉的兩邊沒有公共端點，如圖v1v2，v3v4沒有連線，在v1、v2中任取1點，v3、v4中任取1點，再取v5、v6這兩點，則所得4點即為K4，共有4種取法，即共有4個K4．8．某鎮(zhèn)有居民1000人，每人每天把昨天聽到的消息告訴自己認識的人，已知任何消息只要鎮(zhèn)上有人知道，都會經(jīng)過這樣的方式逐漸地為全鎮(zhèn)的人所知道．證明可以選出90名代表，使得同時向他們報告一個消息，經(jīng)過10天，這一消息就為全鎮(zhèn)的人知道．證明用1000個點代表1000個居民，兩名居民相識，則在兩點之間連一線，如此可得一圖，依條件，這個圖是連通圖．若圖中有圈，則我們?nèi)サ羧χ械囊贿吺谷Ρ黄茐亩挥绊憟D的連通性，經(jīng)過有限次這種手續(xù)，可得樹T1000．在T1000中取一條主干v1v2…vn，取v11作為1個代表，并把邊v11v12去掉，則此圖分成了2個連通分支，在含有v1的一棵樹中，每點到v11的道路的長度都不超過10，否則v1v2…vn在T1000中不是主干，這是不可能的，故v11知道的消息在10天后整個樹的點集所代表的居民全都知道；余下另一分支再取其主干，又按此法得出第二個代表v22，依此類推，則T1000分割成若干棵樹：同樣，在含v22，v33，…的樹中，v22，v33，…知道的消息在10天后整個樹的點集代表的居民全都知道；由于1000=11×90+10，故這樣分法，至多分出89棵樹，余下至多21個點的鏈長≤20，取此鏈的中心，則此中心的離徑≤10．現(xiàn)在取v11，v22，v33，…為代表，只要將消息告訴這些代表，則在10天之后，這些樹的點集所表示的居民全都知道這個消息；最后一棵樹取其中心為代表，該中心到樹中其他各點的距離不超過10，取這個中心所表示的居民作為第90名代表，則問題已獲解決．9．求滿足下列條件的最小正整數(shù)n：在圓周上任取n個點A1、A2、…、An，則在Ceq\o(\s\up5(2),\s\do3(n))個角∠AiOAj(1≤i＜j≤n)中，至少有2007個不超過120°．解：對于這n個點，設(shè)使∠AiOAj＞120°(1≤i＜j≤n)的角共有Sn個，則有Ceq\o(\s\up5(2),\s\do3(n))－Sn個角不超過120°．現(xiàn)求Sn的最大值．規(guī)定：當(dāng)且僅當(dāng)∠AiOAj＞120°時，在Ai與Aj間連一線段．于是共連出了Sn條線段．對于這n個點中的任意3點Ai、Aj、Ak(1≤i＜j＜k≤n)，如果已在這三點間連了2條線段，例如AiAj、AjAk連了線段，則Ai與Ak必不連線．這是因為∠AiOAj＞120°，∠AjOAk＞120°，則必有∠AiOAk＜120°．這說明這Sn條連出的線段中沒有連出三角形．由于在n個點中，至多可以連[eq\f(n2,4)]條線段而沒有連出三角形．于是，Sn≤[eq\f(n2,4)]．于是，解Ceq\o(\s\up5(2),\s\do3(n))－[eq\f(n2,4)]≥2007．若n＝2m，則得m(2m－1)－m2≥2007m≥46若n＝2m＋1，則得(2m＋1)(m＋1)－m(m＋1)≥2007m≥45經(jīng)驗證91滿足要求：把圓周6等分，在相對的兩個等分中放入91個點，其中一個等分放入45個點，另一個等分中放入46個點，在同一等分中的兩個點所對應(yīng)的角＜120°，不同等分中的兩個點所對應(yīng)的角＞120°，即有Ceq\o(\s\up5(2),\s\do3(45))＋Ceq\o(\s\up5(2),\s\do3(46))＝2025個角不超過120°．而90個點中至多有2Ceq\o(\s\up5(2),\s\do3(45))＝1980個角不超過120°．故所求n的最小值為91．10．某次體育比賽，每兩名選手賽一場，無平局．通過比賽確定優(yōu)秀選手．設(shè)A為選手，如果對其他任意選手B，要么A勝B，要么存在選手C，使得A勝C，C勝B，則A即是優(yōu)秀選手．證明：如果按上述規(guī)則選出的優(yōu)秀選手只有1名，則這名選手勝其他所有的選手．證明：取A為勝場最多者，則或A勝所有選手，此時A為優(yōu)秀選手．若A未全勝，則A必負于某個選手B，此時若找不到C，使A勝C而C勝B，即所有負于A的選手都負于B，則B比A勝場更多，矛盾．故必存在這樣的C勝B．故此時A為優(yōu)秀選手．若只有1名優(yōu)秀選手，即優(yōu)秀選手只有A，于是其余選手均不是優(yōu)秀選手．若A負于B，由于B不是優(yōu)秀選手，則存在D，D勝A與B，若D不存在．即其余所有選手或負于A，或負于B，則B也為優(yōu)秀選手．故D必存在．現(xiàn)D勝A、B，由于D不是優(yōu)秀選手，同理，故必能找到E，勝A、B、D，…，這樣一直下去，最后必有一人勝所有其余的人，為優(yōu)秀選手，與只有1名優(yōu)秀選手矛盾．故A全勝．11．凸n邊形及其n－3條在形內(nèi)不相交的對角線組成的圖形稱為一個剖分圖．證明：當(dāng)且僅當(dāng)n是3的倍數(shù)時，存在一個剖分圖是一個可以一筆畫的圈．解：顯然n=6時存在滿足要求的剖分圖，設(shè)凸3k邊形存在滿足要求的剖分圖，對于凸3k+3邊形，可先擦去相鄰3點A2、A3、A4，把余下3k點組成凸3k邊形的剖分圖畫出（從點A1出發(fā)并回到A1)，再把去掉三點補回，并連A1A3，A3A5，即得到3k+3邊形的剖分圖．滿足要求．即當(dāng)n再證明：當(dāng)存在剖分時，3|n．由于是一筆畫的圈，故每個頂點都是偶數(shù)度．于是從每個頂點引出的對角線都有偶數(shù)條．這樣就可以把每個分成的三角形染色，使相鄰的三角形不同色．這時，由于每個頂點處分成的三角形都有奇數(shù)個從而位于兩邊的三角形同色，設(shè)同紅．即只要有原來的凸n邊形邊的三角形都是紅色．而每條對角線兩邊都是異色．統(tǒng)計紅色三角形的邊，若紅色三角形共有k個，紅邊共有3k條，其中凸n邊形的邊有n條，對角線有n－3條，則n+n－3=3k．∴3|n．12．已知n(n≥6的偶數(shù))人中任何3人之間至少有兩人互通電話，且每人至多與eq\b\bc\[(\f(n－2,2))個人互通了電話，證明：這n個人總可以分成不相交的兩組，使同一組內(nèi)任何兩人互通了電話．(原題有錯：原題中沒有n為偶數(shù)的條件，當(dāng)n＝2k＋1時，每人至多與eq\b\bc\[(\f(n－2,2))＝eq\b\bc\[(\f(2k－1,2))＝k－1人通話，但n個人分成不交兩組，總有一組人數(shù)≥k+1，這一組中的人無法都通過話．若改為eq\b\bc\[(\f(n－1,2))，仍不對，只對n為偶數(shù)成立)解：用n個點表示這n個人，若兩人通電話，則在表示這兩人的點間連1條線．題目就是：任意3點中至少連了1條線，每個點至多連eq\b\bc\[(\f(n－1,2))條線．則可以把這些點分成兩個不相交的子集，同集中任意兩點都連了線．任取沒有連線的兩點A1與B1，則與A1沒有連線點的至少有n－1－eq\b\bc\[(\f(n－1,2))＝eq\b\bc\[(\f(n,2))個．設(shè)A1與B1，B2，…，Beq\s\do4()沒有連線，同時可設(shè)B1與A1，A2，…，Aeq\s\do4()沒有連線．令S1＝{A1，A2，…，Aeq\s\do4()}，S2＝{B1，B2，…，Beq\s\do4()}．1若S1∩S2≠，取C∈S1∩S2，則(A1，B1，C)都沒有連線，與“已知任何3人中至少有兩人通了電話”矛盾，故S1∩S2＝．2取三點組(A1，Bi，Bj)(1≤i＜j≤eq\b\bc\[(\f(n,2)))，則只能Bi與Bj連線，即S2中任何兩點都連了線．同樣，S1中任何兩點都連了線．當(dāng)n＝2k(k∈N*)時，S1∪S2＝S，結(jié)論成立．13．給定平面上無三點共線的n個點，以這n個點為兩個端點連出了m條線段，已知對于其中任意的兩點A、B，都有一個點C，使C與A、B都連有線段．求m的最小值．分析：n＝3時，m＝3；n＝4時，m＝5；解：若某點只連了1條線段，例如點A1只連了1條線段A1A2，取A1，A2如果某點恰連了2條線段，如A1只與A2、A3連線，對于A1、A2，則必須連A2A3，成一個三角形．對于點Ai(4≤i≤n)，考慮點對A1、Ai，必有一點與此兩點都連了線，于是Ai必與A2、A3之一連了線．但Ai至少連2條線，故從A4，A5，…，An出發(fā)的線至少有2(n－3)條，且其中至少有n－3條向A2、A3引出．當(dāng)n為奇數(shù)時，除與A2、A3連的線外，其余n－3條線至多重復(fù)2次(在Ai與Aj之間連的線4≤i＜j≤n)，故連的線的條數(shù)m≥3＋(n－3)＋eq\f(1,2)(n－3)＝eq\f(1,2)(3n－3)＝[eq\f(1,2)(3n－2)]；當(dāng)n為偶數(shù)時，其余n－4條線至多重復(fù)2次．故連的線的條數(shù)m≥3＋(n－3)＋eq\f(1,2)(n－4)＋1＝eq\f(1,2)(3n－2)＝[eq\f(1,2)(3n－2)]．如果每個點連線數(shù)都不少于3條，則連線數(shù)≥eq\f(3,2)n．總之，連線數(shù)m≥[eq\f(1,2)(3n－2)]．又，當(dāng)n＝2k＋1(k∈N*)時，連A2h－1A2h(h＝1，2，…，k)，及連AiA2k＋1(i＝1，2，…，n)，共連了3k＝eq\f(1,2)(3n－3)條線，滿足題意；當(dāng)n＝2k(k∈N*)時，連A2h－1A2h(h＝1，2，…，k－1)，及A2An－1，AiAn(i＝1，2，…，n－1)，共eq\f(1,2)(3n－2)條線滿足題意．14．平面內(nèi)是否存在一個含n(n≥8)個點的圖，在這n個點間連有一些線段，使得從n個點出發(fā)的線段數(shù)分別為4，5，6，…，n－5，n－4，n－3，n－2，n－2，n－2，n－1，n－1，n－1?解：n＝8時，如圖可畫出八邊形，其中V1連4條線，V2連5條線，V3、V4、V5連出6條邊，V6、V7、V8連出7條邊．n＝9時在上圖的基礎(chǔ)上增加一個頂點V9，它與V3，V4、V5、V6、V7、V8、V9各連1條邊，則得到連線數(shù)分別為4，5，6，7，7，7，8，8，8的九邊形．當(dāng)n＞9時，設(shè)存在這樣的n邊形V1V2V3…Vn，從其各頂點出發(fā)的線段數(shù)分別為4，5，6，…，n－5，n－4，n－3，n－2，n－2，n－2，n－1，n－1，n－1，去掉Vn、Vn－1、Vn－2三點及所連線段，則余下n－3個點，分別連了1，2，3，…，n－6，n－5，n－5，n－5條線段．取M1＝{V1，V2，V3}；M2＝{V4，…，Vn－6}；M3＝{Vn－5，Vn－4，Vn－3}．由n＞9，故M2≠．由于M3中的點連線數(shù)為n－5，故它們每點僅與1點未連線，若M3中點都沒有與V1連線，則它們都要與V2連線，與V2連2條線矛盾．故V1與M3中某1點連線，設(shè)V1與Vn－3連線，則V2與Vn－4、Vn－5連線(因此二點只與一點未連線)．V3與Vn－5、Vn－4、Vn－3均連線，于是V3與M2中的點均未連線，此時Vn－6至多連了n－3－1－3＝n－7條線，與Vn－6連n－6條線矛盾．故n＞9時這樣的圖不存在．15．某團體中任意兩個認識的人都沒有共同的熟人，而任意兩個不認識的人都恰有兩個彼此共同的熟人．證明：該團體中每個人認識的人數(shù)都相同．解：以n個點表示該團體中的人，兩人認識，則在表示兩人的點間連一條線，問題是：若兩點連了線，則它們不能與同一第三點連線，即不出現(xiàn)三角形，若兩點間未連線，則它們恰與另兩個點都連了線．首先證明任意兩個連線的點的次數(shù)相同．設(shè)AB連線，則它們除彼此外沒有連向同一點，設(shè)A與A1，…，Ak連了線，則A1，…，Ak間均不連線，B與A1，…，Ak均不連線．此時B與Ai除A外必還有一點連線，設(shè)為Bi，且Bi與Bj不同，否則A、Bi與3點都連了線．于是與Ai對應(yīng)的與B連線的點有k個．即|B|≥|A|，同理，|A|≥|B|．即|A|=|B|．其次，若C、D未連線，則C、D都與E、F連線，則|C|=|E|，|D|=|E|，于是|C|=|E|=|F|．于是得證．又證：用n個點表示這n個人，如果其中某兩個人互相認識，則在表示這兩個人的點間連一條線，，這樣就得到了一個圖G．設(shè)其中一人v1有k個熟人，v2，v3，…，vk＋1為其熟人，而與vk＋2，vk＋3，…，vn這n－k－1個人不認識．由已知，v2，v3，…，vk＋1這k個點兩兩不相鄰．此時可知：⑴G中沒有三角形(因如有三角形時，則兩個相鄰的點都與第三點相鄰，與題設(shè)矛盾)⑵若兩點不相鄰，則它們都與某兩個點相鄰，即出現(xiàn)一個四邊形且無對角線的圈．現(xiàn)v1與vk＋2不相鄰，則存在一個以v1及vk＋2為相對頂點的四邊形圈．此四邊形的另兩個頂點與v1都相鄰，故必在v2，v3，…，vk＋1中．不妨設(shè)為v2與v3.(因v1與vk＋2，vk＋3，…，vn這n－k－1個點不相鄰)再考慮v1與vk＋3，也存在一個以v1及vk＋3為相對頂點的四邊形圈，同理，此四邊形的另兩個頂點也必在v2，v3，…，vk＋1中．但不能是v2與v3．否則v2，v3有至少3個共同的熟人v1，vk＋2，vk＋3．這說明與v1不相鄰的頂點至多有Ceq\o(\s\do3(k),\s\up5(2))個，即n－k－1≤Ceq\o(\s\do3(k),\s\up5(2))＝eq\f(k(k－1),2)．⑶又因v2，v3不相鄰，他們有一個共同的熟人v1，另一個共同的熟人不能在v2，v3，…，vk＋1中，只能在vk＋2，vk＋3，…，vn這n－k－1個人中．而v2，v3，…，vk＋1中的不同的二人組，除v1外的另外一個熟人也不同．即二人組數(shù)應(yīng)不超過n－k－1，即n－k－1≥Ceq\o(\s\do3(k),\s\up5(2))＝eq\f(k(k－1),2)．于是n－k－1＝Ceq\o(\s\do3(k),\s\up5(2))＝eq\f(k(k－1),2)．∴k2＋k－2(n－1)＝0．此方程至多只有一個正整數(shù)根．而對每個頂點此方程均成立．即：每個參加者都有同樣多的熟人．⑷△＝1＋8(n－1)＝8n－7為完全平方數(shù)時本題才有解．16．由n個點和這些點之間的l條連線段組成一個空間圖形，其中n=q2＋q＋1，l≥eq\f(1,2)q(q＋1)2＋1，q≥2，q∈N．已知此圖中任四點不共面，每點至少有一條連線段，存在一點至少有q＋2條連線段．證明：圖中必存在一個空間四邊形(即由四點A、B、C、D和四條連線段AB、BC、CD、DA組成的圖形)．(2004年全國聯(lián)賽題)分析：本題是在例13的基礎(chǔ)上進一步加強的題．兩者比較：若取q＝11，則n＝112＋11＋1＝133，l≥eq\f(1,2)11122＋1＝793．但加了條件：“每點至少連有一條線段，存在一點至少連有13條線段”．“無四點共面”即“無三點共線”．證明：設(shè)點集為V＝{A0，A1，…，An－1}，與Ai連線的點集為Bi，且|Bi|＝bi．于是1≤bi≤n－1．又顯然有eq\o(\s\do7(i＝0),\s\up11(n－1),∑)bi＝2l≥q(q＋1)2＋2．若存在一點與其余點都連線，不妨設(shè)b0＝n－1．則B0中n－1個點的連線數(shù)l－b0≥eq\f(1,2)q(q＋1)2＋1－(n－1)(注意：q(q＋1)＝