سوال ۴

ثابت کنید به ازای هر گراف چندگانه دوبخشی $G$ که تمام درجه‌های آن زوج است، می‌توان طوری عدد $+1$ یا $-1$ را به‌یال‌های $G$ نسبت داد به‌طوری که:

  • به ازای هر یال $e$ مجموع عدد روی $e$ و تمام یال‌هایی که حداقل یک سر مشترک با یال $e$ دارند، حداقل یک باشد.
  • مجموع اعداد روی همه‌ی یال‌ها حداکثر $n$ باشد. (که $n$ تعداد راس‌های گراف $G$ است).