چند ضلعی ساده‌ی (بدون حفره‌) $P$ را شبکه‌ای گوییم، اگر رئوس آن مختصات صحیح داشته باشند و اضلاع آن افقی یا عمودی باشند. به وضوح $P$ شامل تعدادی مربع واحد است. حال گرافی به این صورت از روی $P$ می‌سازیم:

به ازای هر مربع واحد از $P$، یک راس قرار می‌دهیم و دو راس را با یال به هم وصل می‌کنیم اگر خانه‌های متناظر، مجاور ضلعی باشند. به گراف حاصل $G_p$ می‌گوییم.

1. ثابت کنید $G_p$ گرافی دو بخشی است.
2. گرافی دو بخشی و همبند مانند $G$ مثال بزنید که درجه هر راس از آن حداکثر ۳ باشد، ولی چند ضلعی شبکه‌ای $P$ موجود نباشد به طوری که: $G=G_P$.
3. همه چندضلعی‌های شبکه‌ای مثل $P$ را بیابید که تعداد راس‌های یکی از بخش‌های $G_P$ بیش از سه برابر تعداد راس‌های بخش دیگر آن باشد.

• سوال بعد
• سوال قبل