初中數(shù)學(xué)競(jìng)賽專(zhuān)題復(fù)習(xí) 第四篇 組合 第29章 圖論初步試題 新人教版

《初中數(shù)學(xué)競(jìng)賽專(zhuān)題復(fù)習(xí) 第四篇 組合 第29章 圖論初步試題 新人教版》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《初中數(shù)學(xué)競(jìng)賽專(zhuān)題復(fù)習(xí) 第四篇 組合 第29章 圖論初步試題 新人教版（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第29章 圖論初步 29.1.1* 某大型晚會(huì)有2009個(gè)人參加，已知他們每個(gè)人至少認(rèn)識(shí)其中的一個(gè)人．證明：必有一個(gè)人至少認(rèn)識(shí)其中的二個(gè)人． 解析 2009這個(gè)數(shù)目較大，我們先考慮：某小型晚會(huì)有5人參加，已知他們每個(gè)人至少認(rèn)識(shí)其中的一個(gè)人．證明：必有一個(gè)人至少認(rèn)識(shí)其中的二個(gè)人． 用5個(gè)點(diǎn)、、、、表示5個(gè)人，如果兩個(gè)人彼此認(rèn)識(shí)（本章中的“認(rèn)識(shí)”都是指相互認(rèn)識(shí)），就在表示這兩個(gè)人的頂點(diǎn)之間連一條邊．對(duì)頂點(diǎn)功來(lái)說(shuō)，由于所表示的人至少認(rèn)識(shí)其他4個(gè)人的一個(gè)，不妨設(shè)與認(rèn)識(shí)，即和相鄰，同樣，設(shè)與相鄰，如圖所示．對(duì)于頂點(diǎn)來(lái)說(shuō)，無(wú)論它與、、、哪個(gè)相鄰，都會(huì)出現(xiàn)一個(gè)頂點(diǎn)引出兩條邊的情況．于是問(wèn)題得

2、以解決． 用同樣的方法可以證明，對(duì)2009個(gè)人來(lái)說(shuō)，命題成立．其實(shí)，把2009換成任意一個(gè)大于l的奇數(shù)，命題也成立． 29.1.2* 在一間房子里有（>3）個(gè)人，至少有一個(gè)人沒(méi)有和房子里每個(gè)人握手，房子里可能與每個(gè)人都握手的人數(shù)的最大值是多少？ 解析 用個(gè)頂點(diǎn)表示個(gè)人，若某兩個(gè)人握過(guò)手，就在他們相應(yīng)的頂點(diǎn)之間連一條邊，這樣就得到了一個(gè)圖．因?yàn)椴皇侨魏蝺蓚€(gè)人都握過(guò)手，所以的邊數(shù)最多是完全圖（即個(gè)點(diǎn)每?jī)牲c(diǎn)之間恰連一條邊）的邊數(shù)減1，去掉的那條邊的兩個(gè)端點(diǎn)和所表示的兩個(gè)人未握過(guò)手．所以房子里可能與每個(gè)人都握手的人數(shù)的最大值是． 29.1.3*** 九名數(shù)學(xué)家在一次國(guó)際數(shù)學(xué)會(huì)議上相遇

3、，發(fā)現(xiàn)他們中的任意三個(gè)人中，至少有兩個(gè)人可以用同一種語(yǔ)言對(duì)話(huà)．如果每個(gè)數(shù)學(xué)家至多可說(shuō)三種語(yǔ)言，證明至少有三個(gè)數(shù)學(xué)家可以用同一種語(yǔ)言對(duì)話(huà)． 解析 用9個(gè)點(diǎn)，，…，表示這九名數(shù)學(xué)家，如果某兩個(gè)數(shù)學(xué)家能用某種語(yǔ)言對(duì)話(huà)，就在他們相應(yīng)的頂點(diǎn)之間連一條邊并涂以相應(yīng)的顏色．我們要證明的是：存在三個(gè)頂點(diǎn)、、，使得邊（，）和（，）是同色的．這樣的，、、這三名數(shù)學(xué)家就能用同一種語(yǔ)言對(duì)話(huà)． 下面就頂點(diǎn)，分兩種情形： （1）與，…，均相鄰，由于每個(gè)數(shù)學(xué)家至多能說(shuō)三種語(yǔ)言，所以每一個(gè)頂點(diǎn)引出的邊的顏色至多是三種．根據(jù)抽屜原理知，從發(fā)出的8條邊中至少有2條是同色的，不妨設(shè)為（，）、（，）．于是、、所表示的三名數(shù)學(xué)

4、家能用同一種語(yǔ)言對(duì)話(huà)．見(jiàn)圖（）． （2）與，，…，中的至少一點(diǎn)不相鄰，不妨設(shè)功與功不相鄰．由于任意三個(gè)數(shù)學(xué)家中，至少有兩個(gè)人可以用同一種語(yǔ)言對(duì)話(huà)，所以，，，…，中的每一個(gè)不是和研相鄰就是和功相鄰，根據(jù)抽屜原理可知，其中至少有4個(gè)點(diǎn)與或相鄰．不妨設(shè)、、、與相鄰，如圖（），再對(duì)引出的這4條邊用抽屜原理可得，至少有2條邊是同色的，設(shè)為（，）、（，）．于是、、所表示的三名數(shù)學(xué)家能用同一種語(yǔ)言對(duì)話(huà)． 評(píng)注 若本題中的九改成八，則命題不成立．反例如圖（）所示．圖中每條邊旁的數(shù)字表示不同的語(yǔ)種． 29.1.4** 證明任何一群人中，至少有兩個(gè)人，它們的朋友數(shù)目相同． 解析 設(shè)任意給定的

5、一群人有個(gè)．用頂點(diǎn)表示這個(gè)人．當(dāng)且僅當(dāng)頂點(diǎn)、表示的兩個(gè)人是朋友時(shí)令、相鄰，得到個(gè)頂點(diǎn)的簡(jiǎn)單圖． 對(duì)中任意，由于它可以和其他個(gè)頂點(diǎn)相鄰，所以頂點(diǎn)的度（）滿(mǎn)足，即圖的頂點(diǎn)度只能是個(gè)非負(fù)數(shù)0，1，…，中的一個(gè)．如果圖的頂點(diǎn)的度都不相同，則圖具有0度頂點(diǎn)和度頂點(diǎn)．度頂點(diǎn)和中其他頂點(diǎn)都相鄰，特別地和頂點(diǎn)相鄰．但0度頂點(diǎn)和中任何頂點(diǎn)都不相鄰，矛盾．這就證明了中必定有兩個(gè)頂點(diǎn)，它們的度相同．也就是說(shuō)，這群人必有兩個(gè)人，他們的朋友一樣多． 29.1.5*** 有一個(gè)參觀(guān)團(tuán)，其中任意四個(gè)成員中總有一名成員原先見(jiàn)過(guò)其他三名成員．證明：在任意四名成員中，總有一名成員原先見(jiàn)過(guò)所有成員． 解析 用圖論語(yǔ)言表示

6、即：圖的任意四點(diǎn)中至少有一個(gè)頂點(diǎn)和其他三個(gè)頂點(diǎn)相鄰．證明圖任意四個(gè)頂點(diǎn)中至少一個(gè)頂點(diǎn)和中其他所有頂點(diǎn)都相鄰． 用反證法．如果命題不成立，則中有四個(gè)點(diǎn)、、、，它們和圖中的其他所有頂點(diǎn)不都相鄰．于是存在四個(gè)頂點(diǎn)、、、（不一定不同）它們依次與、、、都不相鄰．如圖．所以不是、、中的一個(gè)，且與是兩個(gè)不同的頂點(diǎn)． 如果與不同，則、、、中沒(méi)有一個(gè)頂點(diǎn)和其他三個(gè)頂點(diǎn)都相鄰，和已知矛盾．所以和重合．同理可證，和重合．于是和、、都不相鄰，和已知矛盾． 這就證明了圖中任意四個(gè)頂點(diǎn)中至少有一個(gè)頂點(diǎn)和的其他所有頂點(diǎn)都相鄰． 29.1.6** 是否存在這樣的多面體，它有奇數(shù)個(gè)面，每個(gè)面有奇數(shù)條棱？ 解析

7、 不存在這樣的多面體．事實(shí)上，如果這樣的多面體存在，那么用頂點(diǎn)表示這個(gè)多面體的面，并且僅當(dāng)、所代表的兩個(gè)面有公共棱時(shí)，在圖相應(yīng)的兩頂點(diǎn)之間連一條邊，依題意是奇數(shù)，于是奇數(shù)個(gè)奇數(shù)和也是奇數(shù)．而這一個(gè)圖中的頂點(diǎn)的和為偶數(shù)矛盾． 評(píng)注 關(guān)于圖的頂點(diǎn)和邊數(shù)之間的關(guān)系，有如下定理：圖中邊數(shù)的兩倍等于頂點(diǎn)度數(shù)之和．即若中個(gè)頂點(diǎn)為，，…，，邊數(shù)為，則 ． 29.1.7* 名選手進(jìn)行對(duì)抗賽，每名選手至多賽一場(chǎng)，每場(chǎng)兩名選手參加，已賽完場(chǎng)．證明：至少有一名選手賽過(guò)三次． 解析 把選手看成頂點(diǎn)．當(dāng)且僅當(dāng)、所代表的兩名選手比賽過(guò)時(shí)，令、相鄰，得到含個(gè)頂點(diǎn)的簡(jiǎn)單圖．由于總共賽過(guò)場(chǎng)，所以，圖的邊數(shù)是．于是

8、 ． 如果圖中所有頂點(diǎn)的度都不超過(guò)2，則由上式得到 ， 這不可能．因此圖中至少有一個(gè)頂點(diǎn)，它的度至少是3．于是，頂點(diǎn)所表示的選手至少賽過(guò)三次． 29.1.8** 一航空線(xiàn)路共連結(jié)50個(gè)城市，現(xiàn)要求從一個(gè)城市到另一城市至多需換乘兩次飛機(jī)，問(wèn)航空線(xiàn)路最少要多少條（任兩城市之間的航空線(xiàn)路數(shù)為0或1）？ 解析 不妨將50個(gè)城市看成50個(gè)點(diǎn)，它們之間連的線(xiàn)構(gòu)成一連通圖．圖論告訴我們，如果每一點(diǎn)的度（即出發(fā)的線(xiàn)條數(shù)）至少為2，則由于邊數(shù)為點(diǎn)度之和的一半，其數(shù)值不小于50；若有一個(gè)點(diǎn)的度為1（顯然連通圖不存在度為0的孤立點(diǎn)），則可通過(guò)刪去該點(diǎn)證明。邊數(shù)必須至少為49，否則圖就不連通（只需對(duì)剩

9、下的圖不斷進(jìn)行上述處理過(guò)程）．于是找到一個(gè)城市為中轉(zhuǎn)站，其他城市與之相連，構(gòu)成一“星形”即可．故線(xiàn)路最少要49條． 29.1.9 已知九個(gè)人，，…，中，和兩個(gè)人握過(guò)手，、各和四個(gè)人握過(guò)手，、、、各和五個(gè)人握過(guò)手，、各和六個(gè)人握過(guò)手．證明：這九個(gè)人中一定可以找出三個(gè)人，他們相互握過(guò)手． 解析 用9個(gè)點(diǎn)，，…，表示，，…，這九個(gè)人，若兩個(gè)人握過(guò)手，就在他們相應(yīng)的頂點(diǎn)之間連一條邊，這樣便得到了一個(gè)圖．因?yàn)?，所以存在一個(gè)不同于，，的點(diǎn)與相鄰．顯然≥5．考慮與功相鄰的另外5個(gè)點(diǎn)，若其中任意一點(diǎn)都不與相鄰，則 ， 這不可能．故必有一點(diǎn)與相鄰，從而、、兩兩相鄰．即它們表示的三個(gè)人互相握過(guò)手．

10、 29.1.10* 參加某次學(xué)術(shù)討論會(huì)的共有263個(gè)人，已知每個(gè)人至少和三位與會(huì)者討論過(guò)問(wèn)題．證明：至少有一個(gè)人和四位或四位以上的學(xué)者討論過(guò)問(wèn)題． 解析 用點(diǎn)，，…，表示263個(gè)人，兩個(gè)人討論過(guò)問(wèn)題，就在相應(yīng)的點(diǎn)之間連一條邊，得圖．在圖中，任一頂點(diǎn)的次數(shù)≥3．若沒(méi)有一個(gè)頂點(diǎn)的次數(shù)≥4，則中的所有頂點(diǎn)的次數(shù)都是3．于是，是一個(gè)奇數(shù)，而這應(yīng)是一個(gè)偶數(shù)，所以至少有一個(gè)頂點(diǎn)的次數(shù)≥4．于是命題得證． 29.1.11*** 某地區(qū)網(wǎng)球俱樂(lè)部的20名成員舉行14場(chǎng)單打比賽，每人至少上場(chǎng)一次．求證：必有六場(chǎng)比賽，其12個(gè)參賽者各不相同． 解析 用20個(gè)點(diǎn)表示這20名俱樂(lè)部成員，14條邊表示1

11、4場(chǎng)比賽，得圖．根據(jù)題意， ，，2，…，20． 于是 ． 今在每個(gè)頂點(diǎn)處抹去條邊（一條邊可以同時(shí)在其兩端點(diǎn)處被抹去），抹去的邊數(shù)不超過(guò) ． 故余下的圖中至少還有6條邊，且中每個(gè)頂點(diǎn)的次數(shù)都≤1，所以這6場(chǎng)比賽的參賽者各不相同． 29.1.12*** 34個(gè)城市參加雙人舞比賽（每個(gè)城市一男一女），賽前，某些選手互相握手．同一城市的兩人不握手．后來(lái)，來(lái)自城的男選手問(wèn)其他參賽選手他們與人握手的次數(shù)，得到的答案都不相同．問(wèn)城女選手和多少人握過(guò)手？ 解析 用頂點(diǎn)表示參賽選手．對(duì)于、，當(dāng)且僅當(dāng)、所表示的兩名隊(duì)員握過(guò)手時(shí)，令它們相鄰，得到一個(gè)68個(gè)頂點(diǎn)的簡(jiǎn)單圖．由于同一個(gè)的兩名隊(duì)員之間不

12、握手，所以對(duì)任意，．城男選手用表示．圖中除外尚有67個(gè)點(diǎn)，它們的度各不相同，因此必有一個(gè)點(diǎn)度為0，即和中其他頂點(diǎn)不相鄰．所以若頂點(diǎn)表示的選手和頂點(diǎn)所表示的選手來(lái)自一個(gè)城市，則． 從圖中去掉和，得到含66個(gè)頂點(diǎn)的圖．則是中的頂點(diǎn)，并且除外，其他頂點(diǎn)的度也都不相同．因此和前述證明相同，含有度分別為0和64的頂點(diǎn)和，它們?cè)谠瓉?lái)圖中的度分別為1和65．如此繼續(xù)，可證0≤≤33，圖中含有頂點(diǎn)、，它們的度分別為和，而且所代表的選手來(lái)自同一城市，其中，所以．因此城女選手握手次數(shù)為33． 評(píng)注 本題證明中，將的頂點(diǎn)編號(hào)，按度的非降次序（≤≤…≤）排列，得到（，，…，）稱(chēng)為圖的度序列．利用度序列解題是一種

13、重要方法． 29.1.13*** 有一個(gè)團(tuán)體會(huì)議，有100人參加．其中任意四個(gè)人都至少有一個(gè)人認(rèn)識(shí)三人．問(wèn)：該團(tuán)體中認(rèn)識(shí)其他所有人的成員最少有多少？ 解析 先把問(wèn)題翻譯成圖論語(yǔ)言．把該團(tuán)體的成員視為頂點(diǎn)．對(duì)于任意兩個(gè)頂點(diǎn)、所代表的成員，當(dāng)且僅當(dāng)彼此認(rèn)識(shí)，則在、之間聯(lián)一條邊（即相鄰）．得到一個(gè)含100個(gè)頂點(diǎn)的簡(jiǎn)單圖．已知條件是，圖中任意四個(gè)頂點(diǎn)中都至少有一頂點(diǎn)和其他三個(gè)頂點(diǎn)相鄰．要求圖中度為99的頂點(diǎn)個(gè)數(shù)的最小值． 當(dāng)圖是完全圖時(shí)，每個(gè)頂點(diǎn)的度都是99，所以有100個(gè)度為99的頂點(diǎn)． 當(dāng)圖是非完全圖時(shí)，圖中必有兩個(gè)不相鄰的頂點(diǎn)和．顯然，．因此圖中度為99的點(diǎn)的個(gè)數(shù)≤98． 如果中除

14、和外另有兩個(gè)頂點(diǎn)、不相鄰，則、、和中不存在和其他三個(gè)頂點(diǎn)都相鄰的頂點(diǎn)，與題意矛盾．因此中除、外任意兩個(gè)頂點(diǎn)相鄰．這說(shuō)明對(duì)中除、外的任意點(diǎn)，均有≥97． 如果中除、外的任何都和、相鄰，則．此時(shí)中度為99的頂點(diǎn)個(gè)數(shù)為98． 設(shè)中除、外有個(gè)頂點(diǎn)和、不都相鄰，則有的性質(zhì)知，中除、、外的任意頂點(diǎn)和、、都相鄰．因此≤98，≤98，≤98，＝99．所以中度為99的頂點(diǎn)個(gè)數(shù)為97． 這表明含100個(gè)頂點(diǎn)的簡(jiǎn)單圖中，如果任意四個(gè)頂點(diǎn)中必有一個(gè)頂點(diǎn)和其他三個(gè)頂點(diǎn)都相鄰，那么中至少有97個(gè)度為99的頂點(diǎn)． 回到原問(wèn)題，即得：該團(tuán)體中認(rèn)識(shí)其他所有人的成員最少是97個(gè)． 評(píng)注 本題中的成員數(shù)100改為任意的

15、，其他條件不變，則結(jié)論為該團(tuán)體至少有人認(rèn)識(shí)其他所有人． 29.1.14*** 畢業(yè)舞會(huì)有男女學(xué)生各人參加，．每個(gè)男生都和一些但不是全部的女生跳過(guò)舞，每個(gè)女生也都和一些但非全部的男生跳過(guò)舞．證明：總有兩名男生、和兩名女生、，使得和，和跳過(guò)舞，但和，和都未跳過(guò)舞． 解析 用頂點(diǎn)表示參加舞會(huì)的學(xué)生，男生的全體用來(lái)表示，女生的全體用來(lái)表示．對(duì)任意的、，當(dāng)且僅當(dāng)所表示的男生和女生跳過(guò)舞時(shí)令、相鄰．的頂點(diǎn)之間以及的頂點(diǎn)之間都不相鄰． 已知對(duì)任意的、，都有，，要證明圖中含有兩條沒(méi)有公共端點(diǎn)的邊． 設(shè)是中度最大的頂點(diǎn)，在與不相鄰的的頂點(diǎn)中任選．由于和不相鄰，且，所以和中某個(gè)相鄰．如果和所有與相鄰的

16、頂點(diǎn)相鄰，則，與是中度最大的頂點(diǎn)矛盾．因此，必有是的頂點(diǎn)但和不相鄰．于是邊、沒(méi)有公共端點(diǎn)． 評(píng)注 本題解法有一定典型性，抓住圖中度最大的頂點(diǎn)來(lái)解決問(wèn)題．當(dāng)然，有時(shí)也可以從圖中度最小的頂點(diǎn)入手． 29.1.15*** 設(shè)，，，…，是平面上的6點(diǎn)，其中任3點(diǎn)不共線(xiàn)．如果這些點(diǎn)之間任意連結(jié)了13條線(xiàn)段，求證：必存在4點(diǎn)，它們每?jī)牲c(diǎn)之間都有線(xiàn)段連結(jié)． 解折 將已連結(jié)的13條線(xiàn)段全染成紅色，還未連上的兩條用藍(lán)線(xiàn)連上（因?yàn)樗袃牲c(diǎn)連一線(xiàn)段時(shí)應(yīng)該共有15條）．于是必有一個(gè)同色三角形，現(xiàn)在的藍(lán)色線(xiàn)只有兩條，所以同色三角形必為紅色的．不妨設(shè)△是紅色的． 從、、引向△頂點(diǎn)各有3條，這9條線(xiàn)段中最

17、多只有2條藍(lán)色，起碼有7條是紅色的，因此，或者是，或者是，或者是，引向△頂點(diǎn)的線(xiàn)段全是紅色．比如說(shuō)，、、全是紅色，那么4點(diǎn)、、、的每2點(diǎn)連線(xiàn)全是紅色的，命題得證． 29.1.16** 在某城有若干棟（>2）獨(dú)家住宅，其中每棟住宅住有1人．在一個(gè)好天氣，每個(gè)人都將自己的家搬遷了一次．搬遷后每家仍住1人，只是大家都調(diào)換了住宅．證明：在搬遷之后，可將這些住宅分別漆上藍(lán)色、綠色和紅色，使得對(duì)于每個(gè)主人來(lái)說(shuō)，他的新居和舊居顏色不一樣． 解析 將住宅一一編號(hào)，使得第一座住宅搬出來(lái)的人住進(jìn)第二座住宅，第二座住宅出來(lái)的人住進(jìn)第三座住宅……于是一定存在一個(gè)自，使得第矗座住宅搬出的人住進(jìn)第1座住宅．這是個(gè)

18、人形成一個(gè)“圈”．如果志為偶數(shù)，顯然只需要2種顏色，如果＆是奇數(shù)，3種顏色足夠了．然后再考慮其他人，最后形成一個(gè)個(gè)互相獨(dú)立的“圈”（當(dāng)然也可能只有一個(gè)），每個(gè)圈獨(dú)自處理即可． 29.1.17*** 某俱樂(lè)部共有99名成員，每一個(gè)成員都聲稱(chēng)只愿意和自己認(rèn)識(shí)的人一起打橋牌．已知每個(gè)成員都至少認(rèn)識(shí)67名成員．證明一定有4名成員，他們可以在一起打橋牌． 解析 作一個(gè)圖：用99個(gè)點(diǎn)表示99名成員，如果兩名成員相互認(rèn)識(shí)，就在相應(yīng)的兩個(gè)頂點(diǎn)之間連一條邊．已知條件是：對(duì)任意頂點(diǎn)，≥67．欲證中含有一個(gè)4階完全圖． 在中任取一個(gè)頂點(diǎn)，由于≥67，所以存在頂點(diǎn)，使得與相鄰且與不相鄰的頂點(diǎn)至多為（99－1

19、－67＝）31個(gè)．同樣，與不相鄰且與相鄰的頂點(diǎn)也至多31個(gè)．于是圖中至少有（99－31－31－2＝）35個(gè)頂點(diǎn)和、均相鄰．如圖所示，設(shè)頂點(diǎn)和頂點(diǎn)、均相鄰．由于≥67，并且中至多只有（3l+31+2＝）64個(gè)不同時(shí)和、均相鄰的頂點(diǎn)，因此頂點(diǎn)至少還和一個(gè)與、均相鄰的頂點(diǎn)相鄰．從而、、、是4個(gè)兩兩相鄰的頂點(diǎn)．于是命題得證． 評(píng)注l 若將題中的67人改為66人，則不一定能找出4個(gè)互相認(rèn)識(shí)的人來(lái)．反例如圖所示．將頂點(diǎn)集分成三個(gè)子集{，，…，}，{，，…，}，{，，…，）．同一個(gè)子集中任意兩頂點(diǎn)均不相鄰，不同子集中的任意兩點(diǎn)均相鄰．顯然每個(gè)頂點(diǎn)的度都是66，任意4點(diǎn)中，至少有2點(diǎn)屬于同一子集，從而

20、它們不相鄰．也就是說(shuō)圖中不存在兩兩相鄰的4頂點(diǎn)． 評(píng)注2 本題可推廣為： 俱樂(lè)部有（≥4）人，其中每人都至少認(rèn)識(shí)其中的個(gè)人，則在這個(gè)人中必定可以找到4個(gè)人，他們是兩兩認(rèn)識(shí)的． 29.1.18*** 已知五個(gè)城市兩兩相連所得的10條道路中，至少有一個(gè)交叉路口，如圖（）．又已知三個(gè)村莊和三個(gè)城市相連所需的9條道路中，至少有一個(gè)交叉路口，如圖（）．利用上述結(jié)論，問(wèn)：用15條道路把六個(gè)城市兩兩相連，至少會(huì)產(chǎn)生多少個(gè)交叉路口？ 解析 如圖（），至少會(huì)有3個(gè)交叉路口． 假設(shè)最多只有兩個(gè)交叉路口．我們可以去掉兩條路使其余的路不產(chǎn)生交叉路口．考慮以下兩種情況． （1）若去掉的路與同一個(gè)城市相連． 考慮其余的五個(gè)城市，它們兩兩相連．但是根據(jù)已知條件，至少有一個(gè)交叉路口，矛盾． （2）若去掉的兩條路不與同一個(gè)城市相連． 選取其中一條去掉的路所關(guān)聯(lián)的兩個(gè)城市，再取一個(gè)與去掉的路不相連的城市，稱(chēng)這三個(gè)城市為村莊．則這三個(gè)村莊和三個(gè)城市有路相連．由已知條件，必有一個(gè)交叉路口，矛盾． 8