تمرین ۲۲ بخش ۴ از فصل یازدهم کتاب گریمالدی :
الف) فرض کنید [tex]G=(V,E)[/tex] گراف همبند بیطوقه ای باشد که در آن [tex]|V|\ge11[/tex] . ثابت کنید که یا G یا مکمل آن [tex]G^-[/tex] باید نامسطح باشد.
ب) نتیجه قسمت (الف) در واقع به ازای هر [tex]|V|\ge9[/tex] درست است، ولی اثبات آن به ازای [tex]|V|=9[/tex] و [tex]|V|=10[/tex] بسیار دشوارتر است. به ازای [tex]|V|=8[/tex] یک مثال نقض برای قسمت (الف) بیابید.
من با اثبات و مثال نقض مشکلی ندارم.
سوالم اینه :
من یه اثباتی بدست آوردم که نشون می ده به ازای [tex]|V|[/tex] برابر ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ می توان گرافی رسم نمود که خود و مکملش مسطح هستند و این به این معنی است که قضیه مطرح شده در قسمت الف به ازای تعداد راس های ۹ و ۱۰ درست نیست و این با ادعای آورده شده در قسمت (ب) در تناقض است.
اثبات مورد نظر به صورت زیر است :
قصد داریم گراف هایی را بیابیم که خود و مکمل آن ها مسطح است. بنابراین طبق فرع قضیه اویلر خواهیم داشت :
[tex]e\le3v-6[/tex]
و چون مکمل آن نیز مسطح است خواهیم داشت :
[tex]\frac{v(v-1)}{2}-e\le3v-6[/tex]
در نتیجه از ترکیب این دو خواهی داشت :
[tex]\frac{v(v-1)}{2}-3v 6\le e\le3v-6[/tex]
در نتیجه خواهیم داشت :
[tex]\frac{v(v-1)}{2}-3v 6\le3v-6[/tex]
بنابراین خواهیم داشت :
[tex]V^2-13V 24\le0[/tex]
ریشه های معادله فوق برابر با ۲ و خورده ای و ۱۰ و خورده ای است. بنابراین به ازای V های ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ این رابطه درست خواهد بود.
یعنی به ازای تعداد راس های ۹ و ۱۰ نیز گراف هایی موجود می باشند که هم خود و هم مکمل آن مسطح باشند. و این با قسمت ب در تناقض است.
اشتباهم چیست ؟
سلام. یه نکته بگم که اون رابطه شرط کافیه برای مسطح نبودن. همون k3,3 هم طبق رابطه نشون نمیده که مسطح نیست.
(۱۳ مرداد ۱۳۹۳ ۰۱:۱۱ ق.ظ)Jooybari نوشته شده توسط: سلام. یه نکته بگم که اون رابطه شرط کافیه برای مسطح نبودن. همون k3,3 هم طبق رابطه نشون نمیده که مسطح نیست.
بله حق با شماست. فهمیدم اشتباهم کجاست.