תשובה
לא יתכן. הוכחה:
בגרף שמקיים 3n-6 קשתות כל הפאות הם "משולשים" ( במובן שפאה תחומה על ידי 3 קשתות).
נניח שבגרף כזה יש רק 2 קודקודים איזוגיים והם שכנים.
נסמן את הקודקוד הראשון האיזוגי ב A ויש לו קשתות ל K שכנים B1 B2 B3 ....BK כאשר K אי זוגי ו B1 דרגה אי זוגית ושאר הקודוקדים B2...BK דרגה זוגית וגם הם שכנים במעגל כלומר B1 שכן של B2 ששכן ל B3 ששכן ל .... עד חזרה ל B1 ( נובע מזה שכל הפאות משולים)
אז A וB1 הם שכנים ואיזוגיים וכל שאר הקודוקדים ( כולל B2...BK) זוגיים.
נסלק את הנקודה A מהגרף ואת K הקשתות שמתחברים אליה.
הקודקוד B1 הפך להיות זוגי והקודקדים B2...BK לאיזוגיים.
נחבר את B2 ב K-3 קשתות ל B4 B5....BK , כעת B2 נשאר בדרגה איזוגית (כי הוספנו לו K-3 קשתות ו K-3 אי זוגי כי K אי זוגי ), גם B3 נשאר אי זוגי ( לא חיברנו אליו קשת מ B2 כי הוא כבר שכן שלו )
קיבלנו גרף חדש עם n-1 קודקודים שמקיים שמספר הקשתות הוא 3 כפול n-1 פחות 6 ( כלומר שוב גרף מישורי שכל פאותיו משולשים ) שיש בו 2 קודקודים אי זוגיים שכנים B2 B3.
נחזור על התהליך שוב ושוב ונקבל כל פעם גרף מישורי עם מספר קודקודים פחות 1 מהקודם שכל פאותיו משולשים ויש בו 2 קודוקדים שכנים אי זוגיים , אבל זה לא יתכן כי שנגיע ל n=2 כל הקודקודים הם בדרגה זוגיית .