یک ماشین در اختیار داریم که با گرفتن عدد ‎$n$‎ گراف ساده‌ای می‌سازد که راس‌هایش مجموعه‌ی ‎$\{1‎, ‎2‎, ‎3,..‎, ‎n\}$‎ هستند. هدف ما این است که با پرسیدن چند سوال از ماشین گراف را پیدا کنیم. در هر پرسش می‌توانیم یک زیر مجموعه فرد عضوی از رئوس گراف را به ماشین بدهیم و از آن رئوس درجه فردِ زیر گراف القایی حاصل از آن مجموعه را، دریافت کنیم.

1. ثابت کنید درصورتی که ‎$n\ge 2$‎، گراف اولیه هر چه که باشد ما نمی‌توانیم آن را به طور یکتا مشخص کنیم.
2. ثابت کنید اگر بدانیم که ماشین فقط گراف‌های ناهمبند را تولید می‌کند، همواره می‌توان گراف اولیه را حدس زد.

• سوال قبل