Coordinated Attack Problem On The Arbitrary Graph
The easiest way to do the reduction is to decompose your graph into two pieces $G_1,G_2$ arbitrarily, let one general "play" $G_1$, and the other one $G_2$. Details left for you.