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

گزاره‌های زیر مفروض‌اند:

الف) فرض کنیم G یک گراف n رأسی با عدد رنگی x(G) و عدد استقلال α(G) باشد. در این‌صورت x(G) ≥ n/α(G) .

ب) فرض کنیم G گرافی است که حداکثر m رأس از درجه حداکثر n دارد و مابقی رئوس از درجه حداکثر k باشند و k < n . در این‌صورت x(G) ≤ m+k+1 .

ج) فرض کنیم d ≥ 3 عدد صحیح و G یک گراف ساده است که درجه تمام رأس‌های آن حداکثر d است و G ، d-رنگ‌پذیر نیست و G گراف با کمترین تعداد رأس با این خاصیت‌هاست. در این‌صورت G رأس برشی ندارد.

چه تعداد از گزاره‌ها درست است؟