Results 1 to 2 of 2

Math Help - a question involving Eular's formula

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    af
    Posts
    2

    a question involving Eular's formula

    G is a planar graph that has n vertices, e edges, r regions, and
    k connected components.

    Show that the Euler's Formula for G can be written as: n - e + r = k + 1.
    (Remember if G is connected, then k = 1, which means Euler's Formula will be degenerated to n - e + r = 2.)

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~

    I am a super-newbie to discrete math, and I don't even know where I should start with this question

    I only know that the Eular's theorem for any connected planar graph is n - e + r = 2.

    But I don't know how could I transform that formula to n - e + r = k + 1.

    any hints or helps will be appreciated, thanks for reading this post






    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: a question involving Eular's formula

    Do you need to derive the Euler's formula for planar graphs with any number of components from the Euler's formula for graphs with one component? This is easy to do by induction on the number of components. If that number is k + 1 for k > 0, break the graph into two subgraphs, with k components and 1 component. Express the number of vertices, edges and regions in the whole graph through the corresponding numbers for the two subgraphs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Problem involving Stirling's formula
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 14th 2011, 09:42 AM
  2. antiderivative involving euler's formula
    Posted in the Calculus Forum
    Replies: 8
    Last Post: December 2nd 2009, 06:57 AM
  3. Proof of probability formula involving AuB
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: November 3rd 2009, 02:21 PM
  4. Eular path and Eular Circut
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 21st 2009, 10:57 PM
  5. Replies: 2
    Last Post: February 8th 2009, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum