1. The problem statement, all variables and given/known data Let G be a planar graph with n vertices, q edges, and k connected components. If there are r regions in a planar representation of G, prove that: n − q + r = 1 + k Hint: Use induction on k. The base case is Euler’s formula. 2. Relevant equations 3. The attempt at a solution Alright, for k=1 n-q+r=2 (this is true due to Euler's formula) now assume that this statement hold for k=p, meaning n-q+r=1+p This is where I get stuck, I don't know how to show it for k=p+1 I am thinking it is something like since it is true for every one connected component, and p connected components that means that just adding one more to p would make the equation true as well. However, I don't know how to show that mathematically.... any help would be great!!