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