---
tags: 數讀
---
# 圖論part2
> [name=W_Ice_Tri] [time=Sun, March 7, 2021] [color=#1f1e33]

[TOC]
## 1. 暖身
#### Example1.1
如圖，試證無論如何移動馬，無法從左圖變成右圖
 
#### Example1.2
試證：六人行，必有三人兩兩認識或三人兩兩不認識(任兩人關係只有認識與不認識兩種)
#### Example1.3
呈上，試證必有兩組三人兩兩認識或三人兩兩不認識
#### Example1.4
九名數學家在一次國際數學會議上相遇，發現他們任意三個人中，至少有兩人可以用同一種語言對話。若每位數學家至多會三種語言，試證至少有三名數學家可以用同一種語言對話。
#### Example1.5
$20$個網球選手進行$14$場單打比賽，每人至少上場一次，證明：必有六場比賽，其中$12$個參賽者皆不同。
#### Example1.6
平面上有$n$條直線，滿足任兩條直線恰交於一點且無三線共點。這些線會將平面分成好幾區，在每一區中各挑一頂點，若有兩區共用同一條邊，則在這兩區中的兩個頂點連上邊。找出所有可能的$n$使得由這些頂點與邊所形成的圖有哈密頓圈。
(20 Korea)
#### Example1.7
$2n$個人中每個人至少認識$n$個人，試證總可以找出$4$個人圍著園中坐下，使得身旁的都是認識的人。
#### Example1.8
有$n$個人互相猜拳，若皆沒有平手，且每個人恰贏$k$場，證明：$n=2k+1$。
#### Example1.9
騎士在西洋棋盤上做定期的巡邏，是否有存在至少一種方法使得巡邏過程中滿足：起點終點在同一個格子，且騎士恰經過一次其餘的格子。
## 2. Turán's Theorem
### Definition (k-部圖)
:::warning
$k$部圖$G_{V_1,V_2...V_k}$滿足：$$\displaystyle{V=\bigcup^k_{i=1}V_i,V_i\cap V_j=\phi(i\neq j)}$$
同理可得完全$k$部圖$K_{V_1,V_2...V_k}$($k=2$稱完全偶圖)
:::
#### Lemma2.1
若$n$階圖中無$K_{m+1}$子圖，則必存在一頂點$V$使得$$d(V)\leq \left\lfloor{\frac{(m-1)n}{m}}\right\rfloor$$
### Definition (圖蘭圖)
:::warning
圖蘭圖$T_m(n)$代表邊數最大的$n$階圖，且圖中無$K_{m+1}$子圖，定義$e_m(n)$為圖靈圖的邊數
:::
### Theorem2.1 (Turán)
:::info
若$n$階圖中無$K_{m+1}$子圖，則邊數最大值為：$$\displaystyle{e_m(n)=\binom{n-k}{2}+(m-1)\binom{k+1}{2}\ ,\ k=\left\lfloor {\frac{n}{m}}\right\rfloor}$$$$e_m(n)=\left\lfloor(1-\frac{1}{m})\frac{n^2}{2}\right\rfloor$$
:::
#### Remark.
$T_m(n)$只有唯一形式
#### Example2.1
試找出最大的$e$使得$G(60,e)$的邊二染色後無長度為$3,5$的環
(TSTST 2014 P5)
## 3. Ramsey's Theorem
### Definition (二染色)
:::warning
$R(r, s)=n$代表最小的頂點數$n$使得在$K_n$藍紅二圖色時，必會存在藍色的$K_r$或紅色的$K_s$
:::
#### Remark3.1
$R(r,s)=R(s,r)$
#### Remark3.2
$r(a,b)\geq max(a,b)$
#### Remark3.3
$R(1,s)=R(s,1)=1$
#### Remark3.4
$R(2,s)=R(s,2)=s$
#### Remark3.5
$R(3,3)=6,\ R(3,4)=9,\ R(3,5)=14,\ R(3,6)=18,\ R(3,7)=23,\ R(3,8)=28,\ R(3,9)=36,\ R(4,4)=18,\ R(4,5)=25$
### Lemma3.1
$R(r, s) \leq R(r − 1, s) + R(r, s − 1)$

當$R(r − 1, s) , R(r, s − 1)$皆為偶數時可以改寫成這樣：
### Lemma3.2
$R(r, s) \leq R(r − 1, s) + R(r, s − 1)-1$
#### Remark3.6
**Remark 3.7- Remark 3.9**其實都不太會用到
#### Remark3.7
$\displaystyle{R(r,s)\leq \binom{r+s-2}{r-1}}$
#### Remark3.8
$R(a,a)\leq a!$
#### Remark3.9
$\displaystyle{R(a,a)\leq \binom{2a-2}{a-1}\leq \frac{4^{a-1}}{\sqrt{a-1}}}$
### Definition (多染色)
:::warning
滿足每個$m$染色的$K_n$都含有同色三角形的最小的$n$，以$n=R_m$記之
:::
#### Remark3.10
$R_1=3,\ R_2=6,\ R_3=17$
#### Remark3.11
$R_k\leq k(R_{k-1}-1)+2$
#### Remark3.12
$R_k\leq 1+\displaystyle{\frac{k!}{2}+\sum_{i=0}^{k-1}\frac{k!}{i!}}$
#### Example3.1
$17$個人以信件溝通，在他們的信中他們只討論三個主題中的一個，每兩個人之間都有討論，證明:存在至少三個人他們之間討論的是同個主題。
#### Example3.2
某星球上有$3 × 2005!$個居民和$2005$種語言，每兩名居民規定只能用其中一種語言 交流。證明:存在三個居民，他們之間可以用同一種語言進行交流。
(06 HK)
#### Example3.3
在$K_9$中，試求最小的$n$使得：將任意$n$條邊上染成紅藍兩色之一，在這$n$邊中都包含一個同色三角形。
#### Problem3.1
證明：二塗色$K_7$中必有兩個無公共邊的同色三角形
#### Problem3.2
把$1,2,3\cdot 16$分成三堆，試證總可以在某一組中找到這樣的兩個數，他們之差與這一組中的某一個元素相同。
## 刷題嘍～
#### Problem4.1
試求最小的$n$，使得任意給定的$n$個無理數中，總存在三個無理數，其中任意兩個數之和仍是無理數。
#### Problem4.2
有$2020$人，每人都只和自己認識的人打橋牌，試求最小的$n$使得當每個人都認識$n$的人時，總可以找到$4$個人可以一起打橋牌。
#### Problem4.3
$300$名選手參加一場比賽，其中兩名參賽者互相認識或互不認識，已知沒有三名選手兩兩認識，且每名選手至多認識其他$n$ 名選手。對於每個正整數$m$ ($1 \leq m \leq n$)，至少存在一名選手恰認識$m$名選手。求$n$的最大值。
(17 MMO)
#### Problem4.4
在$8\times 8$的方格中，若有一對格子滿足：他們兩個以外的$62$個格子可以被$2\times 1$的多米諾填滿。找出所有符合這性質的格子對。
#### Problem4.5
在$G(n,k)$中，若$P$代表此圖中長度為二的道路(walk)數量，試證：$\displaystyle{P\geq\frac{4k^2}{n}}$
#### Problem4.6
大三角形的三個頂點分別塗以$A,B,C$三色。在大三角形內取數點，將他們分為若干個小三角形，將每個小三角形的頂點分別塗以$A,B,C$三色之一，證明：無論如何塗色，皆存在一個小三角形，它的三頂點皆不同。
#### Problem4.7
設$ \,G\,$是個$ \,k\,$邊連通圖。試證存在一種附$ 1,2,\ldots ,k\,$在每條邊上的方法，使得對於度大於$1$的頂點，其所連結的邊上的數字之最大公因數為$1$
(1991 P4)
#### Problem4.8
某俱樂部有$3n+1$人，每兩人可一起玩象棋、圍棋、跳棋之一。已知每個人皆與$n$個人玩象棋、$n$個人玩圍棋、$n$個人玩跳棋，證明：這$3n+1$人中必有這樣的三個人，他們之間有下象棋的、有下圍棋的、有下跳棋的。
#### Problem4.9
有$25$匹馬去賽馬，皆為等速運動，每場比賽至多$5$隻馬上場比賽，試求最少的場數使得能分出第一二三名。
(100 全國能競)
#### Problem4.10
$2020$個人玩遊戲，任兩人都恰玩一場，每場必分勝負，若不存在像郅暟一樣電跟每個人比贏的人，也不存在像我一樣弱跟每個人比都輸的人，試證存在三個人$A$、$B$、$C$，使得$A$贏$B$，$B$贏$C$，$C$贏$A$。
(博翔電)
#### Problem4.11
給定平面上$6$個點，滿足任意取兩個點所連成的線段長皆不相同，試證明：必存在一個三角形其最長邊恰為另一個三角形的最短邊。
(我能競被電到惹)
#### Problem4.12
有$20$支足球隊，第一輪他們分成$10$對互相比賽，第二輪他們亦分成$10$ˇ對互相比賽，試證：在第三輪開賽之前，一定可以找出$10$之球隊，它們兩兩未賽過。
#### Problem4.13
給定空間中$10$個點，其中任意四點不共面，用一些邊來連接部分頂點，若得到的圖形中不包含空間四邊形與三角形，試求邊的最大值。
(16 China)
#### Problem4.14
Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n + 1$ smaller rectangles.
(14 C1)
#### Problem4.15
$2017$ engineers attend a conference. Any two engineers if they converse, converse with each other in either Chinese or English. No two engineers converse with each other more than once. It is known that within any four engineers, there was an even number of conversations and furthermore within this even number of conversations:

i) At least one conversation is in Chinese.

ii) Either no conversations are in English or the number of English conversations is at least that of Chinese conversations.

Show that there exists $673$ engineers such that any two of them conversed with each other in Chinese.
(17 China TST)
#### Problem4.16
$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that $$\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.$$
(10 C5)
#### Problem4.17
一個社團內有$n$個男生和$n$個女生，也些男生和女生互相為好友，有些男生想要脫魯，所以決定邀請女生出去玩，由於男生們生性害羞，所以他們找的女生至少和他們其中一位是朋友，但如果他們能找到的女生人數比男生團的人數少，這次出去玩的活動計畫就不會成功，這組男生就會被稱為可悲魯宅組。

證明對所有$0\leq k<2^n$，都有一種安排男女間朋友關係的方法，使得男生們恰可以形成$k$個可悲魯宅組。

註：據說構造出來這題至少會有$3$分