فرض کنید تنها اطلاعات مربوط به دور‌های همیلتونی را دارید. بین چه گراف‌هایی ممکن است شک کنید؟

اگر برای دو رنگ‌آمیزی $G_1$ و $G_2$ نتیجه برای تمام دور‌های همیلتونی یکسان باشد، نشان دهید برای چهار راس $a, b, c, d$ و یال‌های $ab, bc, cd, da$، تعداد یال‌های قرمز بین $ab, cd$ برابر تعداد یال‌های قرمز بین $bc$ و $da$ است.

برای اثبات راهنمایی بالا، دو دور همیلتونی زیر را در نظر بگیرید. $$a, b, P, c, d, a$$ $$a, c, P^{rev}, b, d, a$$ که $P$ مسیری گذرا از تمام رئوس غیر از این چهار راس باشد، و $P^{rev}$ برعکس آن باشد.

فرض کنید $x_{uv}$ رنگ یال $uv$ در رنگ‌آمیزی اول باشد که اگر قرمز باشد، $x_{uv}=1$ و در غیر این صورت $x_{uv}=0$. مقدار $y_{uv}$ را نیز برای رنگ‌آمیزی دوم به طریق مشابه تعریف می‌کنیم. قرار دهید $w_{uv}=x_{uv}-y_{uv}$. نشان دهید برای هر راس $v$ می‌توان مقدار $a_{uv}$ نه لزوما صحیح را به گونه‌ای نسبت داد که برای هر دو راس $u$ و $v$، $a_u + a_v = w_{uv}$

برای اثبات گزاره‌ی راهنمایی فوق، سعی کنید مقادیر $a_v$ را بسازید.

ابتدا برای سه راس $x, y, z$ سه مقدار $a_x, a_y, a_x$ را طوری بسازید که برای یال‌های میان خودشان مشکلی نباشد.

حال به کمک مقدار $a_x$، برای هر راس دیگری مثل $s$, $a_s$را تعریف کنید و ثابت کنید این مقادیر حکم را برای هر یال برقرار می‌کنند.

بررسی کنید برای چه دسته از مقادیری از $a_v$ ها ممکن است بیش از یک گراف وجود داشته باشد.

اگر یک $a_v=1$ داشته باشیم، هیچ $a_u=1$ ای نمی‌تواند وجود داشته باشد.

در حالت فوق، یال‌های پرسیده شده نباید مولفه‌ی دو راسی تشکیل دهند و نباید دو راس وجود داشته باشند که یالی از آن‌ها مورد پرسش قرار نگیرد.

در صورتی که یک $a_v = \frac{1}{2}$ داشته باشیم، برای هر راس دیگری مثل $u$ داریم $a_u=\frac{1}{2}, -\frac{1}{2}$.

در حالت فوق، یال‌های پرسیده شده نباید تشکیل زیرگراف دوبخشی دهند.

طبق دو لم فوق نشان دهید حداقل ۱۳۴۹ یال برای پرسش لازم است.

برای اثبات گزاره‌ی فوق، از تعداد مولفه‌ها و شکل مولفه‌های همبندی استفاده کنید. حداقل یک مولفه‌ی دور دار نیاز است و کمینه‌ی نسبت راس‌ها به یال‌ها در هر مولفه‌ی دیگر $\frac{2}{3}$ است.

بر اساس کاری که در اثبات فوق انجام دادید، راهی برای یافتن گراف ارائه دهید.