تمرین ۲۲ بخش ۴ از فصل یازدهم کتاب گریمالدی :

الف) فرض کنید $G=(V,E)$ گراف همبند بیطوقه ای باشد که در آن $|V|\ge11$ . ثابت کنید که یا G یا مکمل آن $G^-$ باید نامسطح باشد.
ب) نتیجه قسمت (الف) در واقع به ازای هر $|V|\ge9$ درست است، ولی اثبات آن به ازای $|V|=9$ و $|V|=10$ بسیار دشوارتر است. به ازای $|V|=8$ یک مثال نقض برای قسمت (الف) بیابید.


من با اثبات و مثال نقض مشکلی ندارم.

سوالم اینه :
من یه اثباتی بدست آوردم که نشون می ده به ازای $|V|$ برابر ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ می توان گرافی رسم نمود که خود و مکملش مسطح هستند و این به این معنی است که قضیه مطرح شده در قسمت الف به ازای تعداد راس های ۹ و ۱۰ درست نیست و این با ادعای آورده شده در قسمت (ب) در تناقض است.

اثبات مورد نظر به صورت زیر است :
قصد داریم گراف هایی را بیابیم که خود و مکمل آن ها مسطح است. بنابراین طبق فرع قضیه اویلر خواهیم داشت :
$e\le3v-6$
و چون مکمل آن نیز مسطح است خواهیم داشت :
$\frac{v(v-1)}{2}-e\le3v-6$

در نتیجه از ترکیب این دو خواهی داشت :


$\frac{v(v-1)}{2}-3v 6\le e\le3v-6$
در نتیجه خواهیم داشت :
$\frac{v(v-1)}{2}-3v 6\le3v-6$
بنابراین خواهیم داشت :
$V^2-13V 24\le0$


ریشه های معادله فوق برابر با ۲ و خورده ای و ۱۰ و خورده ای است. بنابراین به ازای V های ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ این رابطه درست خواهد بود.



یعنی به ازای تعداد راس های ۹ و ۱۰ نیز گراف هایی موجود می باشند که هم خود و هم مکمل آن مسطح باشند. و این با قسمت ب در تناقض است.




اشتباهم چیست ؟