سلام.

۱- هر ناحیه حداقل ۵ یال در مرزش داره. هر یال هم فقط میتونه مرز بین ۲ ناحیه باشه. پس به ازای هر دو ناحیه حداقل ۵ یال داریم.
یه قضیه داریم (فکر کنم اویلر) که برای گرافهای مسطح همبند با استقرا ثابت میشه: v-e+r=2 یعنی تعداد رئوس منهای تعداد یالها بعلاوه تعداد نواحی برابر ۲ خواهد بود. با توجه به این دو رابطه داریم:

[tex]v-e r=2[/tex]
[tex]5\times r \leq 2\times e[/tex]

با جایگزینی نسبت ناحیه ها بجای یالها نتیجه میگیریم:

[tex]v-e \frac{2\times e}{5}\geq 2[/tex]
[tex]v\geq 2 \frac{3\times e}{5}[/tex]

باتوجه به مقدار r=35 حداقل مقدار e برابر ۸۸ میشه و تعداد رئوس بزرگتریا مساوی ۵۵ میشه. شاید یه جایی اشتباه داشتم. مطمئنید تعداد نواحی ۵۳ نبود؟


۲- اگه قرار باشه هیچ راسی با درجه حداقل ۵ نداشته باشیم با فرض اینکه تعداد رئوسمون برابر v باشه، مجموع تعداد یالهامون حداقل برابر ۳v میشه. یکی از قضایایی که میشه از رابطه اویلر اثبات کرد اینه که توی هر گراف مسطح ساده رابطه e<=3v-6 برقراره. با جایگزاری حداقل مقدار e در رابطه به تناقض میرسیم. پس در هر گراف همبند حتماً باید راس با درجه کوچکتر از ۶ داشته باشیم.


۳- از همون رابطه در سوال ۲ میشه استفاده کرد. مجموع یالهای گراف G و متممش میشه به اندازه تعداد یالهای گراف کامل یعنی [tex]\binom{11}{2}=55[/tex]. مسلماً یا G و یا متممش حداقل ۲۸ یال دارن. با قرار دادن مقدار e=28 در رابطه سوال ۲ به تناقض میرسیم. در نتیجه حداقل یکی از این دو گراف مسطح نیستن.

اگه توضیحات کافی نبود بیشتر توضیح بدم.