משפט רמזי – הבדלי גרסאות

נתחיל בקודקוד שרירותי <math>\ v_0</math>. בהכרח קיימים לו אינסוף שכנים המחוברים בקשת אדומה, או אינסוף שכנים המחוברים בקשת כחולה. נוכל להניח שקבוצת השכנים האדומים, שאותה נסמן ב-<math>\ V_0</math>, היא אינסופית. כך אפשר להניח, באינדוקציה, שבחרנו קודקוד <math>\ v_i</math> וקבוצה אינסופית <math>\ V_i</math>, שכל קודקודיה מחוברים בקשת אדומה לכל אחד מן הקודקודים <math>\ v_0,\dots,v_{i}</math>. כעת יש שתי אפשרויות: אם קיים <math>\ v_{i+1}\in V_i</math> לו אינסוף שכנים אדומים ב-<math>\ V_i</math>, נבחר אותו ונסמן ב-<math>\ v_V_{i+1} \subseteq V_i</math> את קבוצת הקודקודים המחוברים ל-<math>\ v_{i+1}</math> בקשת אדומה. אם התהליך ממשיך, נקבל באינסופו של דבר סדרה של קודקודים, אשר כל אחד מהם קשור לכל האחרים באמצעות קשת אדומה, היינו תת-גרף אשר כל הקשתות שלו אדומות. אחרת, התהליך נעצר בקבוצה אינסופית <math>\ V_k</math>, אשר לכל אחד מן הקודקודים שלה יש מספר אינסופי של שכנים כחולים ורק מספר סופי של שכנים אדומים. לכן, אם נחזור על התהליך עבור הקשתות הכחולות בקבוצה <math>\ V_k</math>, התהליך לא יעצר ונקבל קבוצה אין סופית של קודקודים שכל שניים ממנה מחוברים בקשת כחולה.