شرط لازم و کافی برای همیلتنی بودن گراف ساده G

[Goharshady]

این مطالب را بخوانید و ایراد کار را تشخیص دهید:
می خواهیم ببینیم گراف G همیلتنی است یا نه ، گراف 'G را به این صورت می سازیم که در 'G به هر یال G یک راس نسبت می دهیم و رئوس متناظر با دو یال از G در 'G مجاورند اگر و تنها اگر یالهای متناظر با آنها در G یک انتهای مشترک داشته باشند. در این صورت G همیلتنی است اگر و تنها اگر 'G اویلری باشد.

اگر می گویید غلط است ، مثال نقض بیاورید!

 

[Goharshady]

باز اشتباه شد ، می خواستم تو ترکیبیات مقدماتی بنویسم.
معذرت می خواهم.

 

[navidjalalmanesh]

مثال نقض : گرافی 4 راسی در نظر بگیرید , راس 1 را به راس های 2 و 3و 4 وصل کنید . حال گراف `G یک گراف کامل 3 راسی است که می دانیم تور اویلری دارد ولی G دور همیلتونی ندارد .

 

[Goharshady]

متشکرم ، کاملا درسته
آقای خلینا ، لطفا این تاپیک را به ترکیبیات مقدماتی انتقال بدهید. ممنون

 

[Goharshady]

حالا فرض کنید به جای گراف ساده گفته باشیم شرط لازم و کافی برای گراف ساده ی G که درخت نباشد.
حالا مثال نقض بیاورید.