سوال ۱۱۸ کنکور ارشد علوم کامپیوتر ۱۴۰۴

اهمیت

۰/۵

از دو گزاره زیر، کدام گزاره درست است؟

الف ـ گراف $G$ با ۸ رأس و ۱۷ یال و عدد رنگی $\chi(G) = 2$ ، وجود دارد.

ب ـ اگر گراف $G$ حداکثر دو دور فرد داشته باشد، آنگاه رأس‌های آن را می‌توان با حداکثر ۳ رنگ، رنگ کرد به گونه‌ای که هیچ دو رأس مجاوری همرنگ نباشند.

#chromatic-number#graph-coloring#bipartite#odd-cycle#complete-bipartite-graph#3-colorable