سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:گراف:سوال ۱
سوال ۱
یک گراف سادهی زوج-رأسی $G$ با مجموعه رئوس $V(G)$ داریم. برای یک زیرمجموعه از رأسها مانند $S$، زیرمجموعهی $N(S)$ از رأسهای خارج $S$، شامل رأسهایی است که دست کم یک یال به $S$ دارند. در این گراف برای هر زیرمجموعه از رأسها مانند $S$ که $S\cup{}N(S)\neq{}V(G)$ داریم: $|N(S)|\ge |S|$. ثابت کنید این گراف یک تطابق کامل دارد.
به یک گراف ۴ رأسی که تنها یک یال نداشته باشد، کایت گوییم. یک گراف سادهی $6n$ رأسی را که هیچ زیرگراف آن (نه لزومن القایی)، کایت نباشد، جبلی مینامیم. بیشینهی تعداد یالهای ممکن برای یک گراف جبلی $6n$رأسی را $f(n)$ مینامیم. ثابت کنید: $9n^2 \le f(n) \le 12n^2$