Question

ثابت کنید یک گراف، گراف اویلری است اگر و فقط اگر گراف همبند باشد و درجه تمام رأس‌های آن زوج باشند؟ مثلا اگر بخواهیم بدون برداشتن مداد از روی کاغذ گراف $k_{4}$ را رسم کنیم تا یال پنجم رو میتونیم رسم کنیم اینجا مشاهده میشه که یک راس درجه ماکسیمم رسیده و یال دیگه ای نیست که توسط اون از این راس خارج بشیم از این میشه استدلال کرد که باید به تعداد دفعاتی که وارد هر راس میشیم بتونیم خارج هم بشیم پس درجه رئوس باید زوج باشه حداقل . شرط همبند بودن هم واضحه.

اما سوال اینجاست که چرا اگر همبند بود و همه رئوس درجه زوج بود حتما اویلری هم هست؟ در واقع چرا نمیتوان گرافی رسم کرد که همبند باشد و درجه همه رئوس آن زوج باشد اما اویلری نباشد؟

Answer 1

در هر گراف دنباله $v_1e_1v_2e_2...v_ne_n$ ($v_i$ ها رأس و $e_i$ ها یال هستند) را یک مسیر (گذرگاه) از رأس $v_1$ به رأس $v_n$ گویند هرگاه یالها تکراری نباشند.اگر $v_1=v_n$ مسیر را بسته گویند.اگر گرافی شامل یک مسیر بسته شامل تمام یالها باشد آن مسیر را اویلری (آن گراف) را اویلری گویند.گراف همبند گرافی است که بین هر دو رآس آن یک گشت (و در نتیجه یک مسیر ) باشد.

قضیه:هر گرافی اویلری است اگر و تنها اگر همبند و درجه هر رآس آن زوج باشد.

اثبات:اگر تعریفها را مرور کنیم با توجه به اینکه هر گراف اویلری دارای مسیری اویلری است پس بین هر دو رآس آن مسیری وجود دارد لزا همبند است.حالا اگر $v_1e_1v_2e_2...v_ne_nv_1$ مسیر اویلری گراف باشدبا ورود به هر رأس از روی یک یال بلافاصله باید به کمک یالی دیگر از آن خارج شویم لزا درجه هر یال زوج است.

برای اثبات برعکس به خاطر طولانی شدن می توانید به صفحه $78$ کتاب نظریۀ گراف و کاربردهای آن باندی مورتی ترجمه ضرابی زاده یا کتاب خوب آشنایی با نظریه گراف داگلاس بی وست ترجمه بیژن شمس صفحه $127$ مراجعه کنید.

$\Box$