How Can Induction Prove Planar Graph Properties?

Your Name]In summary, to prove the statement for k=p+1, we can use induction and split the graph G into two subgraphs: one with p connected components and one with just one connected component. Applying Euler's formula to each subgraph and combining the equations, we can show that the original equation holds true for k=p+1. This completes the induction step and proves the statement for all values of k.
  • #1
dancergirlie
200
0

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!
 
Physics news on Phys.org
  • #2


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.
 

FAQ: How Can Induction Prove Planar Graph Properties?

1. What is a planar graph?

A planar graph is a type of graph that can be drawn on a two-dimensional surface without any of its edges crossing each other.

2. How is planar graph induction used in proofs?

Planar graph induction is a method used to prove statements about planar graphs by breaking down the problem into smaller cases and proving them inductively.

3. Can any statement about planar graphs be proven using planar graph induction?

No, not all statements about planar graphs can be proven using planar graph induction. This method is most effective for proving statements that involve the number of edges or vertices in a planar graph.

4. Is planar graph induction a complicated method?

Planar graph induction can be a complex method, as it involves breaking down a problem into smaller cases and proving them one by one. However, with practice and understanding of the underlying principles, it can be a powerful tool for proving statements about planar graphs.

5. Are there any limitations to planar graph induction?

One limitation of planar graph induction is that it can only be used to prove statements about planar graphs. It cannot be applied to graphs that are not planar. Additionally, it may not be the most efficient method for proving certain statements, as it can involve a lot of steps and cases.

Similar threads

Back
Top