How Can Induction Prove Planar Graph Properties?

[dancergirlie]

Homework Statement

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.

Homework Equations

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!

 

[mighty2000]

Dear fellow scientist,

Your intuition is on the right track. To prove this statement for k = p+1, we can use the fact that the graph G with p+1 connected components can be divided into two subgraphs: one with p connected components and one with just one connected component. This can be done by removing an edge connecting the two subgraphs.

Let's call the subgraph with p connected components Gp and the subgraph with just one connected component G1. We can apply the induction hypothesis to Gp to get the equation:
np - qp + rp = 1 + p

Now, let's focus on G1. Since it has just one connected component, we can apply Euler's formula to get:
n - q + r1 = 2

Now, let's combine the two equations:
np - qp + rp + n - q + r1 = 1 + p + 2

We can simplify this to:
(n + n) - (q + q) + (r + r1) = p + 3

But since G has p+1 connected components, we know that r + r1 = r + 1. So the equation becomes:
2n - 2q + r + 1 = p + 3

We can rewrite this as:
(n - q + r) + 1 = (p + 1) + 1

And we know from the induction hypothesis that n - q + r = 1 + p. So the equation becomes:
1 + 1 = (p + 1) + 1

Which is true! Therefore, we have proven the statement for k = p+1. This completes the induction step and proves the statement for all values of k.

I hope this helps you in your mathematical journey.