Results 1 to 2 of 2

Math Help - question regarding connected planar graph

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

    question regarding connected planar graph

    Let G be a connected planar graph with n vertices (where n >= 3),
    e edges (where e >= 3), r regions, and no cycle of length 3 or less.
    Show that (e =< 2n - 4)

    I've tried to use the handshake formula and the eular's formula to solve this problem, but it doesn't seems like I am doing the right things

    any hints will be appreciated.
    Last edited by discretemath; October 23rd 2012 at 05:58 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: question regarding connected planar graph

    The idea is to first show e >= 2r using the equality 2e = 3r₃ + 4r₄ + ... where rᵢ is the number of regions with i edges. Then use the Euler's formula.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Planar graph
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 21st 2012, 12:43 AM
  2. What is a simply connected and 4-connected graph?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2012, 11:18 AM
  3. Replies: 5
    Last Post: December 22nd 2010, 02:42 AM
  4. Graph Theory Question - Planar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 13th 2010, 10:19 AM
  5. isomorphic graph, planar graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum