在組合數(shù)學(xué)上，拉姆齊(Ramsey)定理是要解決以下的問題：要找這樣一個(gè)最小的數(shù)n，使得n個(gè)人中必定有k個(gè)人相識或l個(gè)人互不相識。
這個(gè)定理以弗蘭克·普倫普頓·拉姆齊命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個(gè)問題》）證明了R(3,3)=6。

已知的拉姆齊數(shù)非常少，保羅·艾狄胥曾以一個(gè)故事來描述尋找拉姆齊數(shù)的難度：“想像有隊(duì)外星人軍隊(duì)在地球降落，要求取得R(5,5)的值，否則便會(huì)毀滅地球。在這個(gè)情況，我們應(yīng)該集中所有電腦和數(shù)學(xué)家嘗試去找這個(gè)數(shù)值。若它們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了?！?BR>
R(3,3)等于6的證明
證明：在一個(gè)K6的完全圖內(nèi)，每邊涂上紅或藍(lán)色，必然有一個(gè)紅色的三角形或藍(lán)色的三角形。
任意選取一個(gè)端點(diǎn)P，它有5條邊和其他端點(diǎn)相連。
根據(jù)鴿巢原理，3條邊的顏色至少相同，不失一般性設(shè)這種顏色是紅色。
在這3條邊除了P以外的3個(gè)端點(diǎn)，它們互相連結(jié)的邊有3條。
若這3條邊中任何一條是紅色，這條邊的兩個(gè)端點(diǎn)和P相連的2邊便組成一個(gè)紅色三角形。
若這3條邊中任何一條都不是紅色，它們必然是藍(lán)色，因此，它們組成了一個(gè)藍(lán)色三角形。
而在K5內(nèi)，不一定有一個(gè)紅色的三角形或藍(lán)色的三角形。每個(gè)端點(diǎn)和毗鄰的兩個(gè)端點(diǎn) 的線是紅色，和其余兩個(gè)端點(diǎn)的連線是藍(lán)色即可。


這個(gè)定理的通俗版本就是友誼定理。

友誼定理

友誼定理（Friendship Theorem）說明：在一群不少于三人的人中，若任何兩人都剛好只有一個(gè)共同認(rèn)識的人，這群人中總有一人是所有人都認(rèn)識的。
在圖論的角度來說，一幅圖，若每個(gè)頂點(diǎn)都跟另一個(gè)頂點(diǎn)剛好只有一個(gè)共同相鄰的頂點(diǎn)，這幅圖中有一個(gè)頂點(diǎn)和其他頂點(diǎn)都相鄰。