สมมติว่าเรามีกราฟสมบูรณ์บน${\displaystyle n}$จุดยอดเราต้องการแสดงให้เห็น (สำหรับค่าที่เล็กพอของ${\displaystyle n}$) เป็นไปได้ที่จะระบายสีขอบของกราฟด้วยสองสี (เช่น สีแดงและสีน้ำเงิน) เพื่อไม่ให้มีกราฟย่อย ที่สมบูรณ์ บน${\displaystyle r}$จุดยอดที่มีสีเดียว (ขอบทุกด้านมีสีเดียวกัน)

ในการทำเช่นนั้น เราจะระบายสีกราฟแบบสุ่ม โดยระบายสีแต่ละขอบอย่างอิสระด้วยความน่าจะเป็น${\displaystyle 1/2}$ของการเป็นสีแดงและ${\displaystyle 1/2}$ของการเป็นสีน้ำเงิน เราคำนวณจำนวนที่คาดหวังของกราฟย่อยสีเดียวบน${\displaystyle r}$จุดยอดมีดังต่อไปนี้:

สำหรับชุดใดๆ ก็ตาม${\displaystyle S_{r}}$ของ${\displaystyle r}$จุดยอดจากกราฟของเรา กำหนดตัวแปร${\displaystyle X(S_{r})}$จะเป็น${\displaystyle 1}$หากขอบทุกด้านท่ามกลาง${\displaystyle r}$จุดยอดมีสีเดียวกัน และ${\displaystyle 0}$มิฉะนั้น โปรดทราบว่าจำนวนของสีเดียว${\displaystyle r}$-กราฟย่อยคือผลรวมของ${\displaystyle X(S_{r})}$เหนือเซตย่อย ที่เป็นไปได้ทั้งหมด${\displaystyle S_{r}}$สำหรับชุดแต่ละชุด${\displaystyle S_{r}^{i}}$ค่าที่คาดหวังของ${\displaystyle X(S_{r}^{i})}$คือความน่าจะเป็นที่ทั้งหมด${\displaystyle C(r,2)}$ขอบใน${\displaystyle S_{r}^{i}}$มีสีเดียวกัน:

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

(ปัจจัยของ${\displaystyle 2}$(เนื่องจากมีสีที่เป็นไปได้สองสี)

หลักการนี้ใช้ได้กับทุกสิ่งทุกอย่าง${\displaystyle C(n,r)}$กลุ่มย่อยที่เป็นไปได้ที่เราอาจเลือกได้ เช่น${\displaystyle i}$ช่วงตั้งแต่${\displaystyle 1}$ถึง${\displaystyle C(n,r)}$ดังนั้นเราจึงได้ว่าผลรวมของ${\displaystyle E[X(S_{r}^{i})]}$โดยรวม${\displaystyle S_{r}^{i}}$เป็น

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

ผลรวมของค่าคาดหวังคือค่าคาดหวังของผลรวม ( โดยไม่คำนึงว่าตัวแปรจะเป็นอิสระต่อกัน หรือไม่ ) ดังนั้นค่าคาดหวังของผลรวม (จำนวนที่คาดหวังของสีเดียวทั้งหมด)${\displaystyle r}$-กราฟย่อย) คือ

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

ลองพิจารณาดูว่าจะเกิดอะไรขึ้นหากค่านี้น้อยกว่า${\displaystyle 1}$เนื่องจากจำนวนโมโนโครมาติกที่คาดไว้${\displaystyle r}$-กราฟย่อยนั้นน้อยกว่าอย่างเคร่งครัด${\displaystyle 1}$มีการระบายสีแบบหนึ่งที่ตรงตามเงื่อนไขที่ว่าจำนวนของสีเดียว${\displaystyle r}$-กราฟย่อยนั้นน้อยกว่าอย่างเคร่งครัด${\displaystyle 1}$จำนวนของโมโนโครมาติก${\displaystyle r}$- กราฟย่อยในการระบายสีแบบสุ่มนี้เป็น จำนวนเต็มที่ไม่เป็นลบดังนั้นจึงต้องเป็นเช่นนั้น${\displaystyle 0}$(${\displaystyle 0}$เป็นจำนวนเต็มที่ไม่เป็นลบเพียงจำนวนเดียวที่น้อยกว่า${\displaystyle 1}$) ดังนั้นจึงสรุปได้ว่า ถ้า

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(ซึ่งใช้ได้กับกรณีตัวอย่างเช่น...)${\displaystyle n=5}$และ${\displaystyle r=4}$) จะต้องมีการระบายสีแบบหนึ่งที่ไม่มีสีเดียว${\displaystyle r}$-กราฟย่อย^[ก]

ตามนิยามของเลขแรมซีย์สิ่งนี้หมายความว่า${\displaystyle R(r,r)}$ต้องใหญ่กว่า${\displaystyle n}$โดยเฉพาะอย่างยิ่ง${\displaystyle R(r,r)}$ต้องเติบโตอย่างน้อยในอัตราทวีคูณด้วย${\displaystyle r}$.

จุดอ่อนของข้อโต้แย้งนี้คือมันไม่ก่อให้เกิดประโยชน์ ใดๆ เลย ปัญหาการค้นหาการระบายสีดังกล่าวเป็นปัญหาที่ยังไม่ได้รับการแก้ไขมานานกว่า 50 ปีแล้ว

บทความของ Erdős ในปี 1959 (ดูเอกสารอ้างอิงด้านล่าง) ได้กล่าวถึงปัญหาต่อไปนี้ในทฤษฎีกราฟ : เมื่อกำหนดจำนวนเต็มบวกgและkแล้ว จะมีกราฟGที่ประกอบด้วยวัฏจักรที่มีความยาวอย่างน้อยg เท่านั้นหรือไม่ โดยที่จำนวนสีของ กราฟ Gมีค่าอย่างน้อยk ?

สามารถแสดงได้ว่ากราฟดังกล่าวมีอยู่จริงสำหรับgและk ใดๆ และการพิสูจน์นั้นค่อนข้างง่าย ให้nมีขนาดใหญ่มาก และพิจารณากราฟสุ่มGที่มีnจุดยอด โดยที่ขอบทุกเส้นในGมีอยู่ด้วยความน่าจะเป็นp = n ^{1/ g −1}เราจะแสดงว่าด้วยความน่าจะเป็นที่เป็นบวกGจะมีคุณสมบัติสองประการต่อไปนี้:

คุณสมบัติที่ 1. Gประกอบด้วยวัฏจักรที่มีความยาวน้อยกว่า g อย่างมากที่สุดn / 2วัฏจักร

บทพิสูจน์ให้Xเป็นจำนวนวัฏจักรที่มีความยาวน้อยกว่าgจำนวนวัฏจักรที่มีความยาวiในกราฟสมบูรณ์ที่มีnจุดยอดคือ

${\displaystyle {\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}}$

และแต่ละตัวจะปรากฏอยู่ในGด้วยความน่าจะเป็นp ⁱดังนั้นโดยอสมการของมาร์คอฟเราจึงได้ว่า

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

ดังนั้นสำหรับค่า nที่มากพอ คุณสมบัติข้อ 1 จะ เป็นจริงด้วยความน่าจะเป็นมากกว่า1/2

คุณสมบัติข้อ 2. Gไม่มีเซตอิสระที่มีขนาด${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$.

บทพิสูจน์ให้Yเป็นขนาดของเซตอิสระที่ใหญ่ที่สุดในGเห็นได้ชัดว่าเรามี

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

เมื่อไร

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$ดังนั้น สำหรับ ค่า n ที่มากพอ คุณสมบัติข้อ 2 จะเป็น จริงด้วยความน่าจะเป็นมากกว่า1/2

สำหรับค่า nที่มากพอความน่าจะเป็นที่กราฟจากชุดการแจกแจงจะมีคุณสมบัติทั้งสองอย่างจะเป็นค่าบวก เนื่องจากเหตุการณ์สำหรับคุณสมบัติเหล่านี้ไม่สามารถแยกจากกันได้ (หากเป็นเช่นนั้น ผลรวมของความน่าจะเป็นจะมากกว่า 1)

เคล็ดลับอยู่ที่นี่: เนื่องจากG มีคุณสมบัติทั้งสองนี้ เราจึงสามารถลบจุดยอดออก จากGได้มากที่สุดn /2 จุด เพื่อให้ได้กราฟใหม่G′บน${\displaystyle n'\geq n/2}$จุดยอดที่ประกอบด้วยวัฏจักรที่มีความยาวอย่างน้อยg เท่านั้น เราจะเห็นได้ว่ากราฟใหม่นี้ไม่มีเซตอิสระที่มีขนาด${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$G ′สามารถแบ่งออกเป็นเซตอิสระได้อย่างน้อยk เซตเท่านั้น และด้วยเหตุนี้จึงมีจำนวนสีอย่างน้อยkสี

ผลลัพธ์นี้ให้เบาะแสว่าเหตุใดการคำนวณจำนวนสีของกราฟจึงเป็นเรื่องยาก: แม้ว่าจะไม่มีเหตุผลเฉพาะที่ (เช่น วงจรขนาดเล็ก) ที่ทำให้กราฟต้องการสีจำนวนมาก แต่จำนวนสีก็ยังคงมีค่ามากอย่างไม่จำกัด