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!

Homework Help: 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

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