לוח מובילים

יש קשת אחת בין 2 הצמתים בגלל שהגרף פשוט ובגלל שאמרנו שאין להם עוד צומת שכן יכולות להיות רק עוד n-2 קשתות משניהם לשאר הצמתים (לא יכולות להיות 2 קשתות מכל אחד מהם לאותו צומת) http://www.codecogs.com/gif.latex?%7Bm%7D'%20%5Cgeq%20m%20-%20(n-2)%20-%201%20=%20m%20-n%20+1 http://www.codecogs.com/gif.latex?%7Bm%7D'%5Cgeq%20m-n+1

פתרון: נוכיח באינדוקציה על n בסיס (פשוט) נניח נכונות על גרפים בגודל n ונוכיח על גרפים בגודל n+1 ניקח שתי צמתים שמחוברים בקשת v1,v2 ונסתכל על הגרף בעל n-2 הצמתים שלא כולל אותם (ואת הקשתות היוצאות מהן) , נסמן אותו ב-G', ואת מספר הצמתים בו ב-m'. אם יש בו יותר מ- n-2)^2/4) קשתות אז על פי הנחת האינדוקציה יש שם משולש וסיימנו. אחרת יש שם פחות מ- n-2)^2/4) קשתות. נסמן ב-m'' את הקשתות שיוצאות מ- v_1 ו- v_2 ליתר n-2 הצמתים. אזי מתקיים כי: m'+m''+1=m לכן מכיוון ש: m>(n-2)^2/4 ו- m'<(n-2)^2/4 תקבל ש: m''>n וכעת משובך היונים מקבלים שבהכרח יש צומת v_3 שמחובר גם ל-V1 וגם ל-v_2 ולכן יש לך מעגל...

אתה בכיוון. תסתכל על 2 צמתים שכנים בגרף, אם יש להם שכן משותף אז יש קליק בגודל 3. אם לא, תסתכל על הגרף שמתקבל בלי 2 הצמתים האלה והקשתות שמחוברות אליהם. בגרף הזה יש http://www.codecogs.com/gif.latex?n-2 צמתים ומספר הקשתות שלו גדול או שווה ל http://www.codecogs.com/gif.latex?m-(n-1) ואז קצת אלגברה ותקבל שלפי הנחת האינדוקציה יש משולש