1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Planar graph induction proof

  1. Nov 9, 2009 #1
    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

    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

    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!!
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Discussions: Planar graph induction proof
  1. Graph planarity (Replies: 1)

  2. Proof by Induction? (Replies: 2)