To protect my backyard from my neighbor, a biology professor who is sometimes a little overfriendly, I have acquired a large army of vicious robotic dogs. Unfortunately the robotic dogs in this batch...

To protect my backyard from my neighbor, a biology professor who is sometimes a little overfriendly, I have acquired a large army of vicious robotic dogs. Unfortunately the robotic dogs in this batch are very jealous, and they must be separated by fences—in fact, they can’t even face each other directly through a fence. So I have built a collection of n fences to separate my backyard into polygonal regions, where each fence completely crosses my yard (that is, it goes from property line to property line, possibly crossing other fences). I wish to deploy my robotic dogs to satisfy the following property

For any two polygonal regions that share a boundary (that is, are separated by a fence segment), one of the two regions has exactly one robotic dog and the other region has zero robotic dogs. (See Figure 5.15.) Prove by induction on n that this condition is satisfiable for any collection of n fences.